【打卡第201道】【雙指針】【leetCode高頻】：18. 四數之和

1、題目描述

給你一個由 n 個整數組成的數組 nums ，和一個目標值 target 。請你找出並返回滿足下述全部條件且不重複的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個四元組元素一一對應，則認為兩個四元組重複）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意順序 返回答案 。

2、算法分析

這個題和前面的三數之和、最小範圍是一樣的。

使用雙循環 + 雙指針：

求數組中四個數的和，其中符合條件的組合中的和不能重複。

最重要的兩步驟：組合 + 去重

①先對數組進行排序，排序過的數組的元素更好操作

②從第一個元素 i 開始遍曆，遇到重複的就跳過

③再從i + 1開始遍曆如果遇到重複那就跳過

④接著就是雙指針，如果sum == target，那麼將結果添加到結果集中

注意轉換，Arrays.asList(nums[i],nums[j]....)注意添加

⑤在雙指針遍曆的過程中，也需要去重

關於去重：

[1,-1,-1,-1,0,2]，target = 0，那麼第一個-1:[-1,-1,0,2]，和第二個-1[-1,-1,0,2]其實結果都是一樣的。

3、代碼實現

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0;i < nums.length - 3;i++){
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            for(int j = i + 1;j < nums.length - 2;j++){
                if(j > i + 1 && nums[j] == nums[j - 1]){
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while(left < right){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum == target){
                        result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        // 去重
                        while(left < right && nums[left] == nums[left + 1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right - 1]){
                            right--;
                        }
                        left++;
                        right--;
                    }else if(sum > target){
                        right--;
                    }else{
                        left++;
                    }
                }
            }
        }
        return result;
    }
}