LeetCode 18. 4Sum
Sort | Two Pointer
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
.
Notice that the solution set must not contain duplicate quadruplets.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [], target = 0
Output: []
Constraints:
0 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Solution:
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int>>result;
int n = num.size();
sort(num.begin(), num.end());
for (int i = 0; i < n; i++) {
if (i > 0 && num[i-1] == num[i]) {
continue;
}
for (int j = i + 1; j < n; j++) {
if (j > (i + 1) && num[j-1] == num[j]) {
continue;
}
int l = j + 1, r = n - 1;
int partial_sum = num[i] + num[j];
while (l < r) {
int sum = partial_sum + num[l] + num[r];
if (sum < target) {
l++;
} else if (sum > target) {
r--;
} else {
result.push_back({num[i], num[j], num[l], num[r]});
while ((l + 1) < num.size() && num[l] == num[l+1]) l++;
l++;
while ((r - 1) >= 0 && num[r] == num[r - 1]) r--;
r--;
}
}
}
}
return result;
}
};
PreviousLeetCode 17. Letter Combinations of a Phone NumberNextLeetCode 19. Remove Nth Node From End of List
Last updated
Was this helpful?