LeetCode - 3Sum
Problem description
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Analysis
The basic idea is to stuck one as the first selection and choose the other two in the rest of the array. To make sure we don’t have duplicate triplets, we need to sort the array first.
Another key of this problem is to make sure you skip the duplicate item in array, you need to skip for three possible duplicate because it’s 3 Sum.
Here’s the code:
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
public class ThreeSum {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int val = nums[i];
int left = i+1, right = nums.length - 1;
while (left < right){
int sum =val + nums[left] + nums[right];
if (sum == 0){
int finalLeft = left;
int finalRight = right;
res.add(new ArrayList<>(){{add(val);add(nums[finalLeft]);add(nums[finalRight]);}});
// wrong for this part
while (left < nums.length && nums[left] == nums[finalLeft]) {
left++;
}
while (right > -1 && nums[right] == nums[finalRight]) {
right--;
}
}
else if (sum < 0){
left++;
}
else {
right--;
}
}
// wrong for this part
while (i < nums.length && nums[i] == val){
i++;
}
i--;
}
return res;
}
}
What to improve
- need to consider the duplicate item in this problem and should be more careful about the edge case (duplicate item)