Skip to content

Latest commit

 

History

History
43 lines (41 loc) · 1.73 KB

File metadata and controls

43 lines (41 loc) · 1.73 KB

题目: 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。

解题思路:排序+双指针 1、将数组从小到大进行排序 2、指定i的值,不断移动first,和last直到找到所有满足条件的数组 2.1、当三者之和大于0时,说明和过大,last-- 2.2、当三者之和小于0时,说明和过小,first++ 2.3、i++

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    let size = nums.length
    if (size < 3) return []
    let res = []
    nums.sort((a, b) => a - b)  // 将数组从小到大进行排序
    if (nums[0] <= 0 && nums[size - 1] >= 0) {  // 保证排序后的数组有正有负,含全0数组
        let i = 0
        while (i < size - 2) {
            if (nums[i] > 0) break  // 最左侧大于0,无解
            let first = i + 1
            let last = size - 1
            while (first < last) {
                if (nums[i] * nums[last] > 0) break // 三数同号,无解
                let sum = nums[i] + nums[first] + nums[last]
                if (sum === 0) res.push([nums[i], nums[first], nums[last]])
                if (sum <= 0) {  // sum值过小,first后移
                    while (nums[first] === nums[++first]) { }
                } else {  // sum值过大,last前移
                    while (nums[last] === nums[--last]) { }  // 跳过重复值
                }
            }
            while (nums[i] === nums[++i]) { }  // i后移,并且跳过重复值
        }
    }
    return res
};