题解 | #三数之和# [S-P0]

双指针 主要是去重的逻辑有点麻烦
O(n^2), O(1)

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
      Map<Integer, Set<Integer>> m = new HashMap<>();
      ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
      int len = num.length;
      if (len < 3) return ans;
      
      Arrays.sort(num);
      for (int i = 0; i < len-2 && num[i] <= 0; i++) {
        if (i > 0 && num[i] == num[i-1]) continue;
        int cur = num[i];
        int l = i+1, r = len-1;
        while (l < r) {
          int sum = cur + num[l] + num[r];
          if (sum == 0) {
            ans.add(createList(cur, num[l], num[r]));
            // -20 -10 -10 -10  0  0  30  30  30
            // cur  l                         r
            while (l+1 < r && num[l] == num[l+1]) { l++; }
            while (r-1 > l && num[r] == num[r-1]) { r--; }
            // -20 -10 -10 -10  0  0  30  30  30
            // cur          l          r
            l++; r--;
            // -20 -10 -10 -10  0  0  30  30  30
            // cur              l  r
          } else if (sum < 0) {
            while (l+1 < r && num[l] == num[l+1]) { l++; }
            l++;
          } else {  // sum > 0
            while (r-1 > l && num[r] == num[r-1]) { r--; }
            r--;
          }
        }
      }
      return ans;
    }
  
    private ArrayList<Integer> createList(int a, int b, int c) {
      ArrayList<Integer> ar = new ArrayList<>();
      ar.add(a); ar.add(b); ar.add(c);
      return ar;
    }
}