题解 | #三数之和#

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        // 数组排序
        Arrays.sort(num);
        int len = num.length;
        // 固定第一位数，剩下的两位数使用双指针
        for (int i = 0; i < len - 2; i++) {
            int left = i + 1, right = len - 1;
            // 去重
            //至少要有四个数，前面len-2,这里i>0才行 比如这个用例[0,0,0]
            //这里num[i] == num[i - 1] ，不能num[i] == num[i + 1] ,否则会漏情况
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }
            while (left < right) {
                if (num[i] + num[left] + num[right] == 0) {
                    ArrayList<Integer> path = new ArrayList<>();
                    path.add(num[i]);
                    path.add(num[left]);
                    path.add(num[right]);
                    // 符合条件的数组添加到返回的列表中
                    res.add(path);
                    left++;
                    right--;
                    // 去重 注意使用while循环，重复的数组可能不止一个
                    while (left < right && num[left] == num[left - 1]) {
                        left++;
                    }
                    // 去重
                    while (left < right && num[right] == num[right + 1]) {
                        right--;
                    }
                } else if (num[i] + num[left] + num[right] > 0) {
                    right--;
                    // 去重
                    while (left < right && num[right] == num[right + 1]) {
                        right--;
                    }
                } else {
                    left++;
                    // 去重
                    while (left < right && num[left] == num[left - 1]) {
                        left++;
                    }
                }
            }
        }
        return res;
    }
}