3Sum
LeetCode #15 · Medium · Arrays · C++ solution with worked-out approach and complexity analysis.
Approach
Sorting + Two Pointers
Sort the array first. Iterate through the array with index i. For each i, use two pointers (l and r) to find pairs that sum to -nums[i]. Skip duplicates to avoid duplicate triplets.
Time
O(n^2)
Space
O(1) or O(n)
on sorting implementation
Problem description(from LeetCode)
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.
Examples
Example 1
- Input:
- nums = [-1,0,1,2,-1,-4]
- Output:
- [[-1,-1,2],[-1,0,1]]
Constraints
- •3 <= nums.length <= 3000
- •-10^5 <= nums[i] <= 10^5
C++ Solution
solution.cpp
class Solution {
public:
vector<vector<int>> threeSum(vector<int> &nums) {
vector<vector<int>> v;
sort(nums.begin(), nums.end());
for (int i = 0, n = nums.size(); i < n; i++) {
int l = i + 1, r = n - 1;
if (i > 0 && nums[i] == nums[i - 1]) continue;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum > 0) {
r--;
} else if (sum < 0) {
l++;
} else {
v.push_back({nums[i], nums[l], nums[r]});
l++;
while (nums[l] == nums[l - 1] && l < r) {
l++;
}
}
}
}
return v;
}
};