15.三数之和——medium-双指针

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

思路:
三数之和要等于0，则第i元素必须需要小于零，然后定义l和r指针指向i+1和nums.length-1 ，为了保证数组元素的单调性，需要将数组元素按从小到大的顺序排序。

• 如果nums[i] +nums[l] +nums[r] >0,说明r指向的数过大，r左移
• 如果nums[i]+ nums[l]+nums[r] ==0，说明找到答案，注意题目要求不能有重复的三数，l右移，r左移时需要去重。
• 如果 nums[i]+ nums[l]+nums[r] ==0，说明l指向的数过小，l右移
• 如果l>r，说明含有nums[i]的三数和已枚举完，右移i的时候也须去重。

复杂度分析：
时间复杂度O(n)
空间复杂度O(logn) 排序会产生额外的空间复杂度O(logn)

var threeSum = function (nums) {
    const array = [];
    const len = nums.length;
    if (len < 3) return array;
    nums.sort((a, b) => a - b);
    for (let i = 0; i < len; i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let L = i + 1;
        let R = len - 1;
        while (L < R) {
            const sum = nums[i] + nums[L] + nums[R];
            if (sum === 0) {
                array.push([nums[i], nums[L], nums[R]]);
                while (L < R && nums[L] === nums[L + 1]) L++;
                while (L < R && nums[R] === nums[R - 1]) R--;
                L++;
                R--;
            } else if (sum > 0) {
                R--;
            } else {
                L++;
            }
        }
    }
    return array;
};