3Sum LeetCode Solution

·2 mins
leetcode
Author
Mayukh Datta

Given an array `nums` of n integers, are there elements abc in `nums` such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = [] Output: []

Example 3:

Input: nums = [0] Output: []

Constraints:

• `0 <= nums.length <= 3000`
• `-105 <= nums[i] <= 105`

Solution #

class Solution { public: vector<vector> threeSum(vector& nums) {
int n = nums.size(); vector<vector> res;

``````    // we've seen in two sum II problem that sorted array
// makes it easier to solve the problem
sort(nums.begin(), nums.end());

for(int i=0;i<n;i++) {

// to skip duplicates in the sorted array
if(i > 0 && nums\[i\] == nums\[i-1\]) {
continue;
}

// We have to solve a+b+c = 0
// We get the value of 'a' from i
// Using the two pointer approach that we used in
// two sum II, we'll try to find 'b' and 'c'
int start = i + 1, end = n - 1, sum;

while(start < end) {
sum = nums\[i\] + nums\[start\] + nums\[end\];
// sum = a + b + c

if(sum > 0) {
end--;
}else if(sum < 0) {
start++;
}else {
res.push\_back(vector<int>{nums\[i\], nums\[start\], nums\[end\]});

// to skip duplicates present in between the start and end pointers
start++;
while(nums\[start\] == nums\[start - 1\] && start < end) {
start++;
}
}
}
}
return res;
}
``````

};