本文共 2567 字，大约阅读时间需要 8 分钟。

leetcode -15 三数之和

• 題目描述

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

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

• 解 : 雙重指針

思路就是首先將數組排序，接著依序固定一個數字，如果該數已經大於 0，則可以直接返回答案了(因為數組已排序)，否則，利用雙重指針的想法，左右慢慢逼近，直到找到可以使和為 0 的組合，並加入答案數組中，否則，定位下一個元素。具體還是看代碼，如下。

/** * @param {number[]} nums * @return {number[][]} */let threeSum = function(nums) {       let res = []    let sortNums = nums.sort(function(a, b) {    return a-b })    for(let i=0; i
   
     0)            return res                    if(i > 0) {               if(sortNums[i] === sortNums[i-1])                continue        }        const base = sortNums[i]        const target = -base        let left = i+1        let right = sortNums.length-1        while(left < right) {               if(sortNums[left] + sortNums[right] === target) {                   let three = [base, sortNums[left], sortNums[right]]                if(res.length === 0) {                       res.push(three)                }else {                       if(JSON.stringify(res[res.length-1]) !== JSON.stringify(three))                        res.push(three)                }                left++                right--            }else if(sortNums[left] + sortNums[right] > target) {                   right--            }else {                   left++            }        }    }    return res}
   

leetcode -16 最接近的三数之和

• 題目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

• 解 : 解題思路大致上與上一題一樣，也是用到雙重指針的算法。

/** * @param {number[]} nums * @param {number} target * @return {number} */let threeSumClosest = function(nums, target) {       const len = nums.length;    if (len < 3) {           return null;    }    nums.sort(function(a, b){    return a-b })    // 结果，比存储 sum 方便，下面对比时不用再用 target - sum 对比    let res = target - (nums[0] + nums[1] + nums[2])    for (let i = 0; i < len - 2; i++) {           // 左指针为 i+1，右指针为 nums.length - 1        let left = i + 1        let right = len - 1        while (left < right) {               const sum = nums[i] + nums[left] + nums[right]            if (sum === target) {                   return sum;            } else if (sum < target) {                   // sum < target 时，left++                while (nums[left] === nums[++left])            } else {                   // sum > target时，right--                while (nums[right] === nums[--right])            }            // 存储与 target 最近的值            if (Math.abs(sum - target) < Math.abs(res)) {                   res = target - sum            }        }    }    return target - res}