18. 四数之和

18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，__b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 注意： 答案中不可以包含重复的四元组。 示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

解题思路

核心思想：

1. 将原始数组排序。
2. 双层循环遍历数组，固定位置 ，游标 和 根据当前四数之和来进行向右或向左移动。

想到和 【15. 三数之和】类似，只是相比其要多一层循环，所以直接在【三数之和】的基础上修改代码。
还需要注意的是

• 这里的四数之和比较的值是给定的参数 ，而不简单的是 0
• 可能是正数或是负数，提前判断 而直接返回结果，可能会导致漏掉一些解

  class Solution {
  public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();
        if( n < 4 )
            return res;
        //排序nums
        sort(nums.begin(),nums.end());
        //遍历数组
        for(int i=0;i<n;i++) {
            //跳过相同的值
            if(i>0 && nums[i] == nums[i-1])
                continue;
            for(int j=i+1;j<n;j++) {
                //跳过相同的值
                if(j>i+1 && nums[j] == nums[j-1])
                        continue;
                //游标left和right
                int left = j+1;
                int right = n-1;
                while(left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    //得到一个解
                    if( sum == target){
                        vector<int> temp;
                        temp.push_back(nums[i]);
                        temp.push_back(nums[j]);
                        temp.push_back(nums[left]);
                        temp.push_back(nums[right]);
                        res.push_back(temp);
                        //跳过相同的值
                        while(left < right && nums[left] == nums[left+1]){ left++;}
                        while(left < right && nums[right] == nums[right-1]){right--;}
                        left++;right--;
                    //大于target，右游标right向左移
                    }else if( sum > target ){
                        right--;
                    //小于target，左游标left向右移
                    }else{
                        left++;
                    }
                }
            }
        }
        return res;
    }
  };