Fork me on GitHub

leetcode15-3sum解题报告

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

题目

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)

解题思路

  1. 先把无序数组排序
  2. 固定一个数,找出其余两个数让它们的和为固定数的相反数(相加为0)

答案

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
public class Solution {  
List<List<Integer>> ret = new ArrayList<List<Integer>>();

public List<List<Integer>> threeSum(int[] num) {
if (num == null || num.length < 3) return ret;

Arrays.sort(num);

int len = num.length;
for (int i = 0; i < len-2; i++) {
if (i > 0 && num[i] == num[i-1]) continue;
find(num, i+1, len-1, num[i]); //寻找两个数与num[i]的和为0
}

return ret;
}

public void find(int[] num, int begin, int end, int target) {
int l = begin, r = end;
while (l < r) {
if (num[l] + num[r] + target == 0) {
List<Integer> ans = new ArrayList<Integer>();
ans.add(target);
ans.add(num[l]);
ans.add(num[r]);
ret.add(ans); //放入结果集中
while (l < r && num[l] == num[l+1]) l++;
while (l < r && num[r] == num[r-1]) r--;
l++;
r--;
} else if (num[l] + num[r] + target < 0) {
l++;
} else {
r--;
}
}
}
}

Note

这个题目要注意得出的结论可能出现重复的可能,另外要考虑的所有特殊情况如下:

  1. 结果重复
  2. 输入数组长度不够
  3. 输入数组为空
    另外,在搜寻三个数使得其和为0的思路上,不能采取用三个循环的思想,这样会导致时间复杂度很高。可以固定其中的一个数,设置两个指针,让这两个指针移动计算,降低时间复杂度。
-------------本文结束感谢阅读-------------