leetcode 第15题 三数之和

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

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

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

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

解题：
数组取出3个元素总和为 0 并且不能重复

解答思路
1 先排序
2固定一个数，剩余两个做一个双头指针，一头一尾,
3 当三数之和小于目标数则 头指针，向后移动一位，当头指针和前一位相同则继续向前移动避免重复， 当三数之和大于目标数，则尾指针想前移动一位，当尾指针向后一位相同则，继续向后移动避免重复

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
   // 排序减少遍历的循环次数
    nums = nums.sort(sortNumber);
    var number = [];
   // 遍历第一个数
    for (var i = 0; i < nums.length - 2; i++)
    {
        // 当第一个数大于0 由于排序的缘故，剩余数加起来都会大于0
        if (nums[i] > 0)
            break;
       // 如果当前数字和上一个数字相同，上一个数字，已经把当前数字存在的情况已经全部处理过了，所以相同数字直接跳过
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
      // 由于排序的缘故，第二个数字从 i + 1 开始， 第三个数字从末尾开始
        var j = i + 1; var k = nums.length - 1;
     
     // 固定最外层数值 移动 第二个数值和第三个数值
        while(j < k)
        {
           // 如果第三个数字与上个数字相同则必定重复
            if (nums[k] == nums[k+1])
            {
                if (nums[k] == nums[k+1])
                {
                    k--;
                }
                continue;
            }
            if (nums[i] + nums[j] + nums[k] == 0)
            {
                var array = [nums[i], nums[j], nums[k]];
                number.push(array);
                j++;
                k--;
            } 
            // 由于排序缘故，三数之和大于0 说明 nums[k] 太大了，所以要向前移动
            else if (nums[i] + nums[j] + nums[k] > 0)
            {
                k--;
            }
            // 由于排序缘故，三数之和大于0 说明 nums[j] 太小了，所以要向后移动
            else if (nums[i] + nums[j] + nums[k] < 0)
            {
                j++;
            }
        }
    }
    return number;
};

function sortNumber(a,b)
{
    return a - b
}