15.三数之和 18.四数之和

题目:15. 三数之和 - 力扣（LeetCode）

思路:

此题无法沿用两数之和的哈希的方法，因为要考虑到结果去重的问题，这里采用双指针算法。

先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

注意点:一定要用while形式和(right>left)的范围检验，进行去重检查和范围验证

  while((right>left) && (nums[left] == nums[left+1]))left++;while((right>left) && (nums[right] == nums[right-1]))right--

代码:

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>>result;sort(nums.begin(),nums.end());//排序for(int i = 0 ;i < nums.size(); i++){if(nums[i] > 0)return result;//如果最小的数都大于0，就不用进行后面的计算了if(i > 0 && nums[i] == nums[i-1]){continue;}int right = nums.size() - 1;int left = i + 1;while( right > left )//不能是等于，因为要返回三元组，不能让他们相等{if(nums[i] + nums[right] + nums[left] > 0)right -- ;else if(nums[i] + nums[right] + nums[left] < 0)left ++;else{result.push_back(vector<int>{nums[i] , nums[left], nums[right]});while((right>left) && (nums[left] == nums[left+1]))left++;while((right>left) && (nums[right] == nums[right-1]))right--;//进行对b,c的去重left++;right--;//操作完毕，双指针收缩；  }   }}   return result;}
};

题目:18. 四数之和 - 力扣（LeetCode）

思路:由三数变成四数，同样可以用双指针，就是多了一个数多了一层循环，多了一级去重和剪枝

代码:

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>>result;sort(nums.begin(),nums.end());for(int k = 0;k < nums.size() ;k++){if(nums[k] > target && target >= 0)break;if(k > 0 && nums[k] == nums[k-1])continue;for(int i = k+1 ;i < nums.size();i++){if(nums[k]+nums[i] > target && target >= 0)break;if(i > k+1 && nums[i] == nums[i-1])continue;int left = i+1;int right = nums.size()-1;while(right > left){if((long)nums[k] + nums[i] + nums[right] + nums[left] > target )right -- ;else if((long)nums[k] + nums[i] + nums[right] + nums[left] < target)left ++;else{result.push_back(vector<int>{nums[k] , nums[i] , nums[right] , nums[left]});while((right>left) && (nums[left] == nums[left+1]))left++;while((right>left) && (nums[right] == nums[right-1]))right--;left++;right--;}}}}return result;}
};