top15
解法一 暴力解法
无脑搜索，三层循环，遍历所有的情况。但需要注意的是，我们需要把重复的情况去除掉，就是 [1, -1 ,0] 和 [0, -1, 1] 是属于同一种情况的。
publicList<List<Integer>>threeSum(int[] nums) { List<List<Integer>>res=newArrayList<List<Integer>>(); for (inti=0; i<nums.length; i++) { for (intj=i+1; j<nums.length; j++) for (intk=j+1; k<nums.length; k++) { if (nums[i] +nums[j] +nums[k] ==0) { List<Integer>temp=newArrayList<Integer>(); temp.add(nums[i]); temp.add(nums[j]); temp.add(nums[k]); //判断结果中是否已经有 temp 。if (isInList(res, temp)) { continue; } res.add(temp); } } } returnres; } publicbooleanisInList(List<List<Integer>>l, List<Integer>a) { for (inti=0; i<l.size(); i++) { //判断两个 List 是否相同if (isSame(l.get(i), a)) { returntrue; } } returnfalse; } publicbooleanisSame(List<Integer>a, List<Integer>b) { intcount=0; Collections.sort(a); Collections.sort(b); //排序后判断每个元素是否对应相等for (inti=0; i<a.size(); i++) { if (a.get(i) !=b.get(i)) { returnfalse; } } returntrue; }
时间复杂度：n 表示 num 的个数，三个循环 O（n³），而 isInList 也需要 O（n），总共就是 O(n^4)O(n4)，leetCode 复杂度到了 O(n^3)O(n3) 一般就报超时错误了，所以算法还得优化。
空间复杂度：最坏情况，即 O（N）, N 是指 n 个元素的排列组合个数，即 N=C^3_nN=Cn3，用来保存结果。
解法二
参考了这里-Java-solution)
主要思想是，遍历数组，用 0 减去当前的数，作为 sum ，然后再找两个数使得和为 sum。
这样看来遍历需要 O（n），再找两个数需要 O（n²）的复杂度，还是需要 O（n³）。
巧妙之处在于怎么找另外两个数。
最最优美的地方就是，首先将给定的 num 排序。
这样我们就可以用两个指针，一个指向头，一个指向尾，去找这两个数字，这样的话，找另外两个数时间复杂度就会从 O（n²），降到 O（n）。
而怎么保证不加入重复的 list 呢？
要记得我们的 nums 已经有序了，所以只需要找到一组之后，当前指针要移到和当前元素不同的地方。其次在遍历数组的时候，如果和上个数字相同，也要继续后移。文字表述比较困难，可以先看下代码。
publicList<List<Integer>>threeSum(int[] num) { Arrays.sort(num); //排序List<List<Integer>>res=newLinkedList<>(); for (inti=0; i<num.length-2; i++) { //为了保证不加入重复的 list,因为是有序的，所以如果和前一个元素相同，只需要继续后移就可以if (i==0|| (i>0&&num[i] !=num[i-1])) { //两个指针,并且头指针从i + 1开始，防止加入重复的元素intlo=i+1, hi=num.length-1, sum=0-num[i]; while (lo<hi) { if (num[lo] +num[hi] ==sum) { res.add(Arrays.asList(num[i], num[lo], num[hi])); //元素相同要后移，防止加入重复的 listwhile (lo<hi&&num[lo] ==num[lo+1]) lo++; while (lo<hi&&num[hi] ==num[hi-1]) hi--; lo++; hi--; } elseif (num[lo] +num[hi] <sum) lo++; elsehi--; } } } returnres; }
时间复杂度：O（n²），n 指的是 num
空间复杂度：O（N），最坏情况，即 N 是指 n 个元素的排列组合个数，即 N=C^3_nN=Cn3，用来保存结果。
总
对于遍历，这里用到了从两头同时遍历，从而降低了时间复杂度，很妙！
