题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组

题解

排序+双指针法

思路

1. 暴力解法
   最容易想到的就是暴力解法，分三层进行遍历求和，假想左、中、右三个指针在数组上移动，分别代表a、b、c，并且各自位置如名称所示，左指针在最左面，右指针在最后面，中间是中指针，暴力解法如下：
   左指针为最外层遍历，中指针为第二次遍历，右指针为最内侧遍历，例如左指针在数组左边界位置，中指针在左指针+1位置，右指针在中指针+1位置，这是初始位置，然后启动暴力解法，左中指针不动，右指针后移遍历。
   右指针遍历到数组右边界后，中指针后移一位，右指针变为中指针+1位置，然后再开始遍历，最终经过多伦遍历后，中指针也到了数组右边界，然后下一轮左指针后移一位，再次启动三层遍历。
   以上思路最容易想到，但最笨，复杂度最高。
2. 排序+双指针法
   数组经过排序后，最外层左指针的遍历和暴力解法一样不变，变的是中右指针的遍历，由于数组是经过排序的，排序后的数组从左至右升序，这是中右指针运用双指针法的基础。
   • 遍历左指针（假设左指针不动，为最外层遍历）
   • 中右指针进行双指针法遍历
     中指针不动，如果左、中、右加和大于0，说明等于0的结果出现在左侧（左、中指针固定，因此只能右指针左移），右指针左移，直到等于0或者小于0，如果等于0，那么此时的结果就是求解的一组解。
     如果小于0，说明求解结果在右侧（左指针固定，右指针不可能再右移，因为右移后左中右加和又会大于0，因此只能是中指针右移），中指针右移，又移后再次根据左中右加和结果启动新一轮的双指针遍历：
     如果加和大于0，则右指针不断左移，如果等于0就找到一组解，如果小于0，则中指针右移，直到左指针右侧的数组区域都被双指针法扫过为止。
   • 中右指针法遍历后，左指针右移一位，中指针位置又变为左指针+1，右指针位置又变为数组右边界，再次启动新位置的一轮中右指针遍历
     注意，左指针每次变换位置时，需要保证新旧位置的值不同，因为如果相同，那么旧位置时找到的解法，肯定和新位置时的解法是重复的（因为左指针新旧位置的值是一样的）。
     同样中指针也是，左指针固定不变，中指针新旧位置值一样，那旧位置的解也同样是新位置的解，出现重复解。

代码

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 排序
        Arrays.sort(nums);
        // 左指针遍历
        for (int left = 0; left < nums.length; left++) {
            // 如果左指针数值大于0，则左、中、右指针和必定大于0，结束
            if (nums[left] > 0) {
                break;
            }
            // 左指针需要跳过重复出现的数值
            if (left > 0 && nums[left] == nums[left - 1]) {
                continue;
            }
            // 右指针，跟随左指针的变动，每次初始化为数组右边界
            int right = nums.length - 1;
            // 在左指针右侧遍历中指针
            for (int middle = left + 1; middle < nums.length; middle++) {
                // 中指针需要跳过重复出现的数值
                if (middle > left + 1 && nums[middle] == nums[middle - 1]) {
                    continue;
                }
                // 左中右加和如果大于0，在左、中不变的基础上，右指针左移
                while (middle < right && nums[left] + nums[middle] + nums[right] > 0) {
                    right--;
                }
                // 如果中右双指针相遇直接结束中右双指针
                if (middle == right) {
                    break;
                }
                // 如果左中右加和为0，则为要找的值
                if (nums[left] + nums[middle] + nums[right] == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[left]);
                    list.add(nums[middle]);
                    list.add(nums[right]);
                    result.add(list);
                }
            }
        }
        return result;
    }

github