题解 | #三数之和#

如何用双指针解决三数之和问题？

• 求三个数的和可以转换为两个数的和是否等于第三个数的问题，这样可以遍历数组的每个元素，再看能不能从后面的子数组中找两个元素相加等于这个数，这样就转换为两数之和的问题了。
• 由于题目要求三元组非降序排列，所以可以先将数组排序好，然后再遍历元素，当遍历到某个元素时，设置两个指针指向后面子数组的首尾，如果这两个指针的元素相加等于当前元素的负值，说明满足条件，将这三个元素按升序顺序放入三元组中，再将这个三元组存入解集中，再移动首尾指针寻找下一个满足条件的两个元素。如果这两个指针的元素相加大于当前元素的负值，由于数组是有序的，说明右边指针的元素太大了，此时要移动右指针，反之则移动左指针。
• 题目的难点在于解集中的三元组不能重复，因此我们在构造三元组时就要去重，也就是说每次选取的元素不能是跟上一个重复的，而数组是有序的，我们只需判断相邻的元素是否相等就知道下一个元素是否跟当前元素重复了。

自己的做法

遍历数组选取一个数作为另外两个数的和，转换为两数之和的问题。再用一个临时数组存放剩余遍历的元素，在遍历剩余元素的过程中判断当前选取的数减去当前遍历的元素的差是否在临时数组中来确定是否存在满足条件的三元组，如果当前选取的数减去当前遍历的元素的差在临时数组中，则这三个元素可以组成满足条件的三元组。但是这种做法一是去除重复三元组很繁琐，二是三元组可能没按升序存入解集，故放弃。

参考

https://blog.nowcoder.net/n/52f0fe5b8b2041e4a3aff839f93c9dfe?f=comment

https://blog.nowcoder.net/n/718f4e85afcc4661a9db3fc1a1c4cf32?f=comment

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param num int整型一维数组 
 * @return int整型二维数组
 */
export function threeSum(num: number[]): number[][] {
    // write code here
    const res: Array<number[]> = [];
    let left: number;
    let right: number;

    num.sort((a, b)=>a-b);
    for (let i = 0; i < num.length-2; ++i) {
        // 只有当前数值小于0才有可能和其他两个数相加等于0
        if (num[i] > 0) {
            return res;
        }
        // 同一个数不能重复选两次，这样解集中才能不出现重复的三元组
        if (i && num[i] === num[i-1]) {
            continue;
        }

        left = i+1;
        right = num.length-1;
        while (left < right) {
            if (num[left] + num[right] === -num[i]) {
                res.push([num[i], num[left], num[right]]);

                // 先移动指针，再去重，否则可能不满足while循环条件时，指针永远无法移动
                left++;
                right--;
                // 选取下一个跟当前left和right指向的值不重复的值
                while (num[left-1] === num[left]) {
                    left++;
                }
                while (num[right+1] === num[right]) {
                    right--;
                }
            }
            else if (num[left] + num[right] < -num[i]) {
                left++;
            }
            else {
                right--;
            }
        }

    }
    return res;
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // write code here
        // 三数之和转换为两个数相加是否等于另一个数的问题
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        int left;  // 指向后面子数组的左指针
        int right;  // 指向后面子数组的右指针

        Arrays.sort(num);
        
        // 解集中不能有重复的三元组，因此在每次选取新元素时都要进行去重判断
        for (int i = 0; i < num.length-2; ++i) {
            // 只有当前数小于0才有可能跟其他数字相加等于0
            if (num[i] > 0) {
                return ret;
            }
            if (i > 0 && num[i-1] == num[i]) {  // 第一个数不能选取重复的数
                continue;
            }

            // 子数组初始范围
            left = i + 1;
            right = num.length - 1;
            while (left < right) {
                if (num[left] + num[right] == -num[i]) {
                    ArrayList<Integer> temp = new ArrayList<>(Arrays.asList(num[i], num[left], num[right]));
                    ret.add(temp);

                    // 选取下一个左右元素，要进行去重判断
                    left++;
                    right--;
				    // 递增后都要判断left < right，防止越界，left越界后，num会报错
                    while (num[left] == num[left-1] && left < right) {
                        left++;
                    }
                    while (num[right] == num[right+1] && left < right) {
                        right--;
                    }
                }
                else if (num[left] + num[right] > -num[i]) {  // 说明右边值太大
                    right--;
                }
                else {
                    left++;
                }
            }
        }

        return ret;
    }
}