leetcode15-三数之和

leetcode 15

思路

时间复杂度：O(n2) 空间复杂度：O(logn)+O(k)

本题主要考虑使用双指针法解答，遍历i的时候i固定，然后定义两个指针left和right，通过移动left和right来使得总和相加为0，但是有个**前提是需要先将数组进行排序。排序完以后的数组，如果总和发现过小那么我们左指针右移动，因为越向右值越大，如果总和过大，那么右指针左移，找到总和为0，把这三个元素放入答案中。
在不断移动的过程中很重要的一个细节：去重**，因为题目中有说明不可以包含重复的三元组，就是当已经出现过例如[-1,-1,2]这个答案以后，后面不能再出现这个答案，我们对于i,left,right都需要进行去重，i循环的时候如果i的前一个数和当前数是相等我们就要continue，因为如果当前的值和之前的值一样的话，那么后续遍历过的元素，在前一个值那里已经完全遍历过一遍，所以不需要再进行遍历，同样left如果和前一个元素一样，right和后一个元素一样时也是直接continue

图片来自代码随想录

实现

var threeSum = function (nums) {
    // 排序
    nums.sort((a, b) => a - b)
    let result = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) return result;
        // 去重，如果下一个遍历的元素和上一个元素相等，那么后续的元素其实是已经遍历过了
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            // 去重
            if (left > i + 1 && nums[left] === nums[left - 1]) {
                left++;
                continue
            }
            if (right < nums.length - 1 && nums[right] === nums[right + 1]) {
                right--;
                continue;
            }
            let sum = nums[left] + nums[right] + nums[i]
            if (sum === 0) {
                // 目标值
                result.push([nums[i], nums[left], nums[right]])
                left++
            } else if (sum < 0) {
                // 和小了，那么需要把left右移，让总体值变大
                left++;
            } else {
                // 和大了
                right--;
            }
        }
    }
    return result;
};