05 August 2008
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]
]
这个题的意思是在Array中找到三个数加起来为0， 用1-2Sum的双指针的方法来解，先对Array排序，然后拿出第一个index从左到右循环，第二第三个index分别向右向左移动来确定triplet；找到triplet后还需要考虑去除重复triplets的问题，这里直接用了hashset来判断triplet-ArrayList<Integer>是否相同，也可以存到map里面，判断一下如果有相同的key就不存进去。
时间复杂度: O(nlogn) + O(n^2) = O(n^2)；空间复杂度O(n)。
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
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length < 3) {
return results;
}
int len = nums.length;
HashSet<List<Integer>> noDup = new HashSet<>();
Arrays.sort(nums);
List<Integer> oneResult = new ArrayList<>();
for (int first = 0; first < len - 2; first++) {
int second = first + 1, third = len - 1;
while (second < third) {
int sum = nums[first] + nums[second] + nums[third];
if (sum == 0) {
oneResult.add(nums[first]);
oneResult.add(nums[second]);
oneResult.add(nums[third]);
if (noDup.add(oneResult)) {
results.add(oneResult);
}
// 不管是否重复，都要重新设置
oneResult = new ArrayList<>();
second++;
third--;
} else if (sum > 0) {
third--;
} else {
second++;
}
}
}
return results;
}
}
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
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>(); //保持最终结果
HashSet<ArrayList<Integer>> noDuplicateTriplets = new HashSet<ArrayList<Integer>>();//保持中间找到的triplet不要是重复的
if (nums == null || nums.length < 3) {
return result;
}
Arrays.sort(nums);
for (int first = 0; first <= nums.length - 3; first++) {
int second = first + 1, third = nums.length - 1;
//接下来需要确定第二个指针second和第三个指针third是否找到合适的triplet或者相遇
while (second < third) {
int sum = nums[first] + nums[second] + nums[third];
if (sum < 0) {
second++;
} else if (sum > 0) {
third--;
} else { //找到了一个triplet
ArrayList<Integer> oneTriplet = new ArrayList<Integer>();
oneTriplet.add(nums[first]);
oneTriplet.add(nums[second]);
oneTriplet.add(nums[third]);
if (!noDuplicateTriplets.contains(oneTriplet)) {//因为是排好序的，所以找出来的triplet直接跟之前的所有triplets比较一下看看是否重复
//下面这句话也可以作为判断条件
noDuplicateTriplets.add(oneTriplet);//没有重复就加到hashset里面为了接下来比较下一个可能的triplet比较
result.add(oneTriplet);//没有重复同时也加到结果里面
}
//注意这里second和third是同时移动，因为排过序了后找到的是已经等于target了，所以只移动一个index的话是不会再找到非重复的triplet的
second++;
third--;
}
}
}
return result;
}
}