题目描述（中等难度）

解法一 暴力解法

无脑搜索，三层循环，遍历所有的情况。但需要注意的是，我们需要把重复的情况去除掉，就是 [1, -1 ,0] 和 [0, -1, 1] 是属于同一种情况的。 1. public List> threeSum(int[] nums) { 2. List> res = new ArrayList>(); 3. for (int i = 0; i < nums.length; i++) { 4. for (int j = i + 1; j < nums.length; j++) 5. for (int k = j + 1; k < nums.length; k++) { 6. if (nums[i] + nums[j] + nums[k] == 0) { 7. List temp = new ArrayList(); 8. temp.add(nums[i]); 9. temp.add(nums[j]); 10. temp.add(nums[k]); 11. //判断结果中是否已经有 temp 。 12. if (isInList(res, temp)) { 13. continue; 14. } 15. res.add(temp); 16. } 17. } 18. } 19. return res; 20. 21. } 22. 23. public boolean isInList(List> l, List a) { 24. for (int i = 0; i < l.size(); i++) { 25. //判断两个 List 是否相同 26. if (isSame(l.get(i), a)) { 27. return true; 28. } 29. } 30. return false; 31. } 32. 33. public boolean isSame(List a, List b) { 34. int count = 0; 35. Collections.sort(a); 36. Collections.sort(b); 37. //排序后判断每个元素是否对应相等 38. for (int i = 0; i < a.size(); i++) { 39. if (a.get(i) != b.get(i)) { 40. return false; 41. } 42. } 43. return true; 44. }

时间复杂度：n 表示 num 的个数，三个循环 O（n³），而 isInList 也需要 O（n），总共就是 ，leetCode 复杂度到了 一般就报超时错误了，所以算法还得优化。 空间复杂度：最坏情况，即 O（N）, N 是指 n 个元素的排列组合个数，即 ，用来保存结果。

解法二

参考了这里-Java-solution) 主要思想是，遍历数组，用 0 减去当前的数，作为 sum ，然后再找两个数使得和为 sum。 这样看来遍历需要 O（n），再找两个数需要 O（n²）的复杂度，还是需要 O（n³）。 巧妙之处在于怎么找另外两个数。 最最优美的地方就是，首先将给定的 num 排序。 这样我们就可以用两个指针，一个指向头，一个指向尾，去找这两个数字，这样的话，找另外两个数时间复杂度就会从 O（n²），降到 O（n）。 而怎么保证不加入重复的 list 呢？ 要记得我们的 nums 已经有序了，所以只需要找到一组之后，当前指针要移到和当前元素不同的地方。其次在遍历数组的时候，如果和上个数字相同，也要继续后移。文字表述比较困难，可以先看下代码。 1. public List> threeSum(int[] num) { 2. Arrays.sort(num); //排序 3. List> res = new LinkedList<>(); 4. for (int i = 0; i < num.length-2; i++) { 5. //为了保证不加入重复的 list,因为是有序的，所以如果和前一个元素相同，只需要继续后移就可以 6. if (i == 0 || (i > 0 && num[i] != num[i-1])) { 7. //两个指针,并且头指针从i + 1开始，防止加入重复的元素 8. int lo = i+1, hi = num.length-1, sum = 0 - num[i]; 9. while (lo < hi) { 10. if (num[lo] + num[hi] == sum) { 11. res.add(Arrays.asList(num[i], num[lo], num[hi])); 12. //元素相同要后移，防止加入重复的 list 13. while (lo < hi && num[lo] == num[lo+1]) lo++; 14. while (lo < hi && num[hi] == num[hi-1]) hi--; 15. lo++; hi--; 16. } else if (num[lo] + num[hi] < sum) lo++; 17. else hi--; 18. } 19. } 20. } 21. return res; 22. }

时间复杂度：O（n²），n 指的是 num 空间复杂度：O（N），最坏情况，即 N 是指 n 个元素的排列组合个数，即 ，用来保存结果。

总

对于遍历，这里用到了从两头同时遍历，从而降低了时间复杂度，很妙！ 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情