https://leetcode-cn.com/problems/3sum/submissions/
image.png

最优解

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         Arrays.sort(nums);
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         for (int i = 0; i < nums.length - 2; i++) {
  6.             if (nums[i] > 0) {
  7.                 return ans;
  8.             }
  9.             if (i > 0 && nums[i] == nums[i - 1]) {
  10.                 continue;
  11.             }
  12.             int left = i + 1, right = nums.length - 1;
  13.             while (left < right) {
  14.                 int sum = nums[i] + nums[left] + nums[right];
  15.                 if (sum == 0) {
  16.                     ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
  17.                     left++;
  18.                     right--;
  19.                     while (left < right && nums[left] == nums[left - 1]) {
  20.                         left++;
  21.                     }
  22.                     while (left < right && nums[right] == nums[right + 1]) {
  23.                         right--;
  24.                     }
  25.                 } else if (sum > 0) {
  26.                     right--;
  27.                 } else {
  28.                     left++;
  29.                 }
  30.             }
  31.         }
  32.         return ans;
  33.     }
  34. }

先找一个目标值nums[i]，再用双指针扫描剩余。把三数之和转化为两数之和，这里用双指针扫描而不是用两数之和的map方法，原因也是随着目标指针i的右移，剩余长度越来越短，扫描时间可控，同时如果使用map，value也是列表结构，也许进行遍历。
这里还有个疑问，在sum > 0 或 < 0时也可以用while循环去掉重复元素，理论上也不会更慢，但实际计算耗时增加很多。
如果使用双指针+二分查找方式的问题是当sum=0是不确定左右指针的移动方向，需要递归计算。