2,3,n数之和|算法技巧

剑指 Offer 57. 和为s的两个数字

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let left,right;
    left=0;right=nums.length-1;
    while(left<right){
        let sum=nums[left]+nums[right];
        if(sum<target){
            left++;
        }
        else if(sum>target){
            right--;
        }
        else{
            return [nums[left],nums[right]];
        }
    }
};

15. 三数之和

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let ans = [];
    const len = nums.length;
    if(nums == null || len < 3) return ans;
    nums.sort((a, b) => a - b); // 排序
    for (let i = 0; i < len ; i++) {
        if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
        let L = i+1;
        let R = len-1;
        while(L < R){
            const sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                ans.push([nums[i],nums[L],nums[R]]);
                while (L<R && nums[L] == nums[L+1]) L++; // 去重
                while (L<R && nums[R] == nums[R-1]) R--; // 去重
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--;
        }
    }        
    return ans;
};

去重是个大坑。。。

16. 最接近的三数之和

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
     nums=nums.sort((a,b) => a-b);// 先升序排序 此为解题的前置条件
     let left, right;
     let diff,min=99999;
     let result;
     for(let i=0; i<nums.length-2; i++){// 从左往右依次尝试定一个基础指针 右边至少再保留两位 否则无法凑成3个
        let basic=nums[i];
        right =nums.length-1;// 右指针先从数组最后一项开始尝试
        left =i+1;// 左指针先从 i 右侧的第一位开始尝试
        let sum;
        while(left < right){
            sum=nums[left] + nums[right] + basic;
            diff=Math.abs(sum-target);
            if(diff<min){
                min=diff;
                result=sum;//更新最小查与更新sum
            }
            if(sum<target){
                left++;
            }
            else if(sum>target){// 相等的话 差就为0 一定是答案
                right--;
            }
            else return sum;
        }
        
     }
     return result;
 
 
};

https://mp.weixin.qq.com/s/fSyJVvggxHq28a0SdmZm6Q