This question is part of NeetCode150 series.
Problem Description
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.
Solution set must not contain duplicate triplets.
leetcode
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
For the main function:
Sort the input array nums.
Iterate through the array:
If the current value is greater than zero, break from the loop. Remaining values cannot sum to zero.
If the current value is the same as the one before, skip it.
Otherwise, call twoSumII for the current position i.
For twoSumII function:
Set the low pointer lo to i + 1, and high pointer hi to the last index.
While low pointer is smaller than high:
If sum of nums[i] + nums[lo] + nums[hi] is less than zero, increment lo.
If sum is greater than zero, decrement hi.
Otherwise, we found a triplet:
Add it to the result res.
Decrement hi and increment lo.
Increment lo while the next value is the same as before to avoid duplicates in the result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
//Sort the array in ascending order
Arrays.sort(nums);
//Loop through the elements one by one
for(int i=0; i<nums.length; i++){
//Fix the first element
int current = nums[i];
//If the current element is more than 0, triplet will 0 sum is NOT possible (since our array is sorted)
if(current > 0) break;
//If the current element is same as the previous one, skip it since we don't want duplicates
if(i!=0){
if(nums[i] == nums[i-1]) continue;
}
//Let's look for the other two elements such that the total sum of three elements in 0
//We will do this using two pointer approach
int l=i+1, r=nums.length-1;
while(l<r){
//If their sum is less than 0, we need a higher value, so we increment L
if(nums[i] + nums[l] + nums[r] < 0){
l++;
//If their sum is more than 0, we need a lower value, so we decrement R
}else if(nums[i] + nums[l] + nums[r] > 0){
r--;
//We have found our triplet
}else{
List<Integer> tempList = new ArrayList<Integer>();
tempList.add(nums[i]);
tempList.add(nums[l]);
tempList.add(nums[r]);
//Save the current triplet
ans.add(tempList);
//Move to the next elements
l++; r--;
//This part is important to avoid duplicates. If we land into the same element, move forward
while(nums[l] == nums[l-1] && l<r) l++;
}
}
}
return ans;
}
}