https://leetcode-cn.com/problems/3sum/
点击查看【bilibili】

题目

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

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

示例

  1. 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
  3. 满足要求的三元组集合为：
  4. [
  5.   [-1, 0, 1],
  6.   [-1, -1, 2]
  7. ]
Input: nums = []
Output: []

Input: nums = [0]
Output: []

解答

  1. 给数组排序
  2. 遍历数组,从O遍历到 length - 2(为什么?)
  3. 如果当前的数字等于前一个数字, 则跳过这个数(为什么?)

  4. 如果数字不同,则设置 start = i+1, end= length-1,

    查看 i, start和end 三个数的和比0大还是小,<br />       如果比0小,start++, 如果比0大,end--<br />       如果等于0,把这三个数加入到结果里

  5. 返回结果

image.png

答案

var threeSum = function(nums) {
    const result = []
    nums.sort((a,b) => a-b) //排序
    for(let i=0;i<nums.length -2; i++) {
        // 第一个数不需要和前一个数比较，
        // 或者 当前数 不等于 前一个数
        // 满足以上条件开始计算值
        if(i===0 || nums[i] !== nums[i-1]) {
            let start= i+1 ,end= nums.length -1;
            while(start < end) { //当start位置小于end位置，进行求和
                if(nums[i] + nums[start] + nums[end] === 0) {
                    result.push([nums[i],nums[start],nums[end]])
                    start++ 
                    end-- 
                    // 旧的start和新的start不相等才可以
                    while(start<end && nums[start] == nums[start -1]) {
                        start++
                    }
                    while(start<end && nums[end] == nums[end + 1]) {
                        end--
                    }
                }else if(nums[i] + nums[start] + nums[end] < 0) {
                    start++
                }else {
                    end--
                }
            }

        }
    }
    return result
};