Given an array nums
of n integers and an integer target
, are there elements a, b, c, and d in nums
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 nums = [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的解决方式,设立双指针求解
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int len = nums.size(); vector<vector<int>> result; == len) return result; sort(nums.begin(),nums.end()); ; i < len- ; i++){ && nums.at(i) == nums.at(i-)) continue; && nums.at(i) + nums.at(i+)+nums.at(i+)+nums.at(i+) > target) break; && nums.at(i) + nums.at(len-)+nums.at(len-)+nums.at(len-) < target) continue; ; j < len- ; j++){ && nums[j] == nums[j-]) continue; && nums[i] + nums[j] + nums[j+] + nums[j+] > target) break; && nums[i] + nums[j] + nums[len-] + nums[len-] < target) continue; ; ; while(left < right){ int temp = nums.at(i) + nums.at(j) + nums.at(left) + nums.at(right); if(temp == target){ result.push_back({nums.at(i),nums.at(j),nums.at(left),nums.at(right)}); left++; right--; ])//避免重复 left++; ]) right--; }else if(temp < target){ left++; }else{ right--; } } } } return result; } };