15.3Sum.md

15. 3Sum

Medium

https://leetcode.com/problems/3sum/

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题：先排序再双指针

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    //如果小于 3，则结束
    if (nums.length < 3) return [];
  	const list = [];
    //增序
  	nums.sort((a, b) => a - b);
  	for (let i = 0; i < nums.length; i++) {
    	// 如果当前下标的值和上一个值是相同的，则跳过本次
    	if (i > 0 && nums[i] === nums[i - 1]) continue;
    	let left = i;
    	let right = nums.length - 1;

    	// 结果是 [nums[left], nums[right], nums[i]，这三个相加为 0
    	while (left < right) {
            //两个指针不能指向当前下标
            if (left === i) {
                left++;
            } else if (right === i) {
                right--;
            } else if (nums[left] + nums[right] + nums[i] === 0) {
                list.push([nums[left], nums[right], nums[i]]);
                //取得一次结果后，需要对指针进行移动，但如果右移或者左移的过程发现前一个或
                //者后一个等于当前的，那么则忽略这个值，继续往前移动
                //并且进入下一次循环，查找其他可能的值
                while (nums[left] === nums[left + 1]) {
                left++;
                }
                left++;
                while (nums[right] === nums[right - 1]) {
                    right--;
                }
                right--;
                continue;
            } else if (nums[left] + nums[right] + nums[i] > 0) {
                //如果
                right--;
            } else {
                left++;
            }
        }
    }
    return list;
};