每日一题（9）：三数之和

开始

来了，来了，我来了，我还没放弃

今天这道题

乍一看上来先回忆了一下高中数学里的排列组合

这不明摆着要用组合先筛选出所有可能情况

然后一顿累加

最后去重完事？

但是事情往往不像看上去那么...难

其实这道题用双指针也可以做（不得不说双指针真是削减时间复杂度的利器

我们只需要：

• 对数组先进行排序
• 开始遍历
• 先判断当前nums[i]，如果它>0那没什么好说的了，直接结束，因为排过序了，3个正数之和是不会等于0的
• 再令左指针nums[i + 1]，右指针为nums[nums.length - 1]
• 当它们相遇，我们就结束循环
• 开始双指针遍历模式
• 若三数之和等于0，那么我们直接存结果，这里别忘，跳过所有重复值，然后两个指针分别继续向中间靠近
• 若三数之和小于0，说明需要适当加大被加值，右移左指针
• 若三数之和大于0，说明需要适当减小被加值，左移右指针
• 完

下面看看代码实现吧

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }

        // 对数组排序，减少处理复杂度
        Arrays.sort(nums);

        List<List<Integer>> iss = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int curr = nums[i];
            if (curr > 0) {
                // 因为已排序，所以当最小的值大于0时，右侧2个数只会与它相等或更大，3个正数相加不可能等于0，所以退出循环
                break;
            }
            int l = i + 1;
            int r = nums.length - 1;
            if (l == r) {
                // 当左指针右指针指向同一位置，退出循环
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                // 当前一数与当前数相等，则跳过重复值
                continue;
            }
            while (l < r) {
                int left = nums[l];
                int right = nums[r];
                int sum = curr + left + right;
                if (sum == 0) {
                    iss.add(Arrays.asList(curr, left, right));
                    while (l < r && nums[l] == nums[l + 1]) {
                        // 跳过所有重复值
                        l++;
                    }
                    while (l < r && nums[r] == nums[r - 1]) {
                        // 跳过所有重复值
                        r--;
                    }
                    l++;
                    r--;
                } else if (sum < 0) {
                    // 当sum小于0，说明需要适当加大被加值，右移左指针
                    l++;
                } else {
                    // 当sum大于0，说明需要适当减小被加值，左移右指针
                    r--;
                }
            }
        }

        return iss;
    }
}

以及执行效率，时间复杂度：O(n^2)

下次继续