代码随想录 哈希 test 8

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

        与三数之和类似，重点在剪枝和去重的区别，由于target可正可负，因此需要分两种情况讨论，如果target为正，则若当前选择的元素之和大于target，需要跳出这种选择，如果target为负，则若当前选择的元素之和大于target，需要跳出这种选择，可以将这两种情况简化(不完全相同)为判断当前选择的元素之和大于target且选择的元素之和>=0(目标值为-100，若元素为-99，-1，0也可以成立)，去重与之前类似，注意选择第二个元素时同样需要类似的剪枝。

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