Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.Example: given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
题目也是3Sum的升级版，这里可以枚举前两个数，后两个数使用3Sum中的双指针逼近。
class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; if (nums.size() < 4) return result; sort(nums.begin(),nums.end()); for(int i = 0; i < nums.size() - 3; i++) { while (i > 0 && i < nums.size() - 3 && nums[i] == nums[i - 1]) i++; for (int j = i + 1 ; j < nums.size() - 2; j++) { while (j > i + 1 && j < nums.size() - 2 && nums[j] == nums[ j - 1]) j++; int start = j + 1, end = nums.size() - 1; while (start < end) { int sum = nums[i] + nums[j] + nums[start] + nums[end]; if (sum == target) { vector<int> tmp; tmp.push_back(nums[i]); tmp.push_back(nums[j]); tmp.push_back(nums[start]); tmp.push_back(nums[end]); result.push_back(tmp); start++; while(start< end && nums[start] == nums[start - 1]) start++; } else if (sum < target) { start++; while (start < end && nums[start] == nums[start - 1]) start++; } else { end--; while (start < end && nums[end] == nums[end + 1]) end--; } } } } return result; }};新闻热点
疑难解答
