Study Notes

Appearance

相向双指针（一） ​

视频精讲：相向双指针（一）

看完视频，值得学习的点： ​

  • 如何得到思路：用坐标系把有序数组标记出来，把样例或自己造的数据在图上呈现，思考如何用代码得到正确答案。
  • 用 O(1) 的时间得知 O(n)的信息？：每次左右指针之和跟target比较，确定范围；如果大于，删右指针，小于删左
题目代码备注
167. 两数之和 II - 输入有序数组代码
15. 三数之和代码包含两个优化
2824. 统计和小于目标的下标对数目代码*课后作业
16. 最接近的三数之和代码*课后作业
18. 四数之和代码*课后作业
611. 有效三角形的个数代码*课后作业
  • 两数之和
js
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    // 比如，2，4，6，8，9；找8
    // 【2，4】，【2，6】对，【2，8】，抓住有序这一性质，大于target的不用看了；但是左边始终要遍历一遍，
    // 观察发现，指针相向的时候可以减少遍历，大于target就right--，反之同理
    let l = 0, r = numbers.length -1;
    while(1){
        let s = numbers[l] + numbers[r];
        if(s === target) return[l+1,r+1];
        s > target ? r-- : l++;
    }

};
  • 三数之和
    • 遇到的问题：js数组方法不确定：就是push,sort((a,b)=>a-b)
    • 不会去重，j===k重复的情况；把握不住时机
    • 两个优化想不到 优化 优化一：如果 nums[i] 与后面最小的两个数相加 nums[i]+nums[i+1]+nums[i+2]>0，那么后面不可能存在三数之和等于 0，break 外层循环。

优化二：如果 nums[i] 与后面最大的两个数相加 nums[i]+nums[n−2]+nums[n−1]<0，那么内层循环不可能存在三数之和等于 0，但继续枚举，nums[i] 可以变大，所以后面还有机会找到三数之和等于 0，continue 外层循环。

js
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    //target === 0;看样例,
    //容易想到，遍历i+相向指针j，k；
    //难点：怎么确定三元组不重复？
    let ans = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length - 2; i++) {
        let t = -nums[i];
        if (nums[i] === nums[i - 1]) continue;
        if(nums[i+1]+nums[i+2] > t) break;
        let j = i + 1, k = nums.length - 1;

        while (j < k) {
            if (nums[j] + nums[k] === t) {
                // if(nums[j]===nums[j-1]||nums[k]===nums[k-1]) break;
                while (j < k && nums[j] === nums[j + 1]) j++;
                // 关键2：跳过k的重复值
                while (j < k && nums[k] === nums[k - 1]) k--;
                ans.push([-t, nums[j], nums[k]]);
                j++;
                k--;
            }
            else if (nums[j] + nums[k] < t) j++;
            else if (nums[j] + nums[k] > t) k--;
            else continue;
        }
    }
    return ans;
};

作业： ​

  • 小于target的数对个数
js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var countPairs = function (nums, target) {
    //先排序
    nums.sort((a, b) => a - b);
    console.log(nums)
    //-1 1 1 2 3 小于目标值就是移动右边指针,那左边呢，懂了，模拟一遍就知道了
    let l = 0, r = nums.length - 1, ans = 0;
    while (l < r) {

        if (nums[l] + nums[r] > target || nums[l] + nums[r] === target) r--;
        if (nums[l] + nums[r] < target) {
            ans += r - l;
            l++;
            // r = nums.length;
            //这里不用重新赋值是因为我们采用的计算，不是遍历，r没有动，模拟一下就知道了

        }

    }
    return ans;

};
  • 三数之和最接近; 重做
js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
abs = function (x) {
    return x > 0 ? x : -x
}
var threeSumClosest = function (nums, target) {
    nums.sort((a, b) => a - b)
    // let ans = 1000;初始化不对
    let ans = nums[0] + nums[1] + nums[2];
    let tmp = 0, n = nums.length;
    for (let i = 0; i < n - 2; i++) {
        let j = i + 1, k = n - 1;
        //考虑特殊情况，作优化
        if (nums[0] + nums[1] + nums[2] > target) {
            ans = nums[0] + nums[1] + nums[2];
            continue;
        }
        else if (nums[n-1] + nums[n-2] + nums[n-3] < target) {
            ans = nums[n-1] + nums[n-2] + nums[n-3];
            continue;
        }
        while (j < k) {

            tmp = nums[i] + nums[j] + nums[k];
            // console.log('i = ', i, nums[i], nums[j], nums[k], tmp, ans)
            ans = abs(tmp - target) < abs(ans - target) ? tmp : ans;
            //可以利用math.target。
            if (nums[i] + nums[j] + nums[k] < target) j++;
            else if (nums[i] + nums[j] + nums[k] > target) k--;
            else return nums[i] + nums[j] + nums[k]; // 添加这一行，防止进入无限循环
        }
    }
    return ans;
};
  • 四数之和
    • 主要是优化和去重部分，想不到
js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
    //双指针，三层遍历，两层优化？
    //一个优化是极端情况下不用遍历：一二次循环，前几个已经大，后几个已经小
    //然后不会优化：重复情况,外层去重，内层去重
    const n = nums.length - 1;
    let ans = [];
    nums.sort((a, b) => a - b);
    // console.log(nums)
    for (let i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;

        if (nums[i] + nums[n] + nums[n - 1] + nums[n - 2] < target) continue;// 优化2：当前最大值 < target，需要增大 i（continue 而不是 break）
        for (let j = i + 1; j < n - 1; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            // 如果 b>a+1 且 nums[b]=nums[b−1]，那么 nums[b] 和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接 continue。注意这里 b>a+1 的判断是必须的，如果不判断，对于示例 2 这样的数据，会直接 continue，漏掉符合要求的答案。


            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;//打表排错到这里哈哈

            let l = j + 1, r = n;
            while (l < r) {
                console.log('before', nums[i], nums[j], nums[l], nums[r])
                if (nums[i] + nums[j] + nums[l] + nums[r] > target) r--;
                else if (nums[i] + nums[j] + nums[l] + nums[r] < target) l++;
                else if (nums[i] + nums[j] + nums[l] + nums[r] === target) {

                    ans.push([nums[i], nums[j], nums[l], nums[r]]);
                    // ✅ 最小改动：添加这两行去重
                    while (l < r && nums[l] === nums[l + 1]) l++;
                    while (l < r && nums[r] === nums[r - 1]) r--;
                    l++;
                    r--;
                }


                // console.log('after', nums[i], nums[j], nums[l], nums[r])

            }

        }


    }

    return ans;
};
  • 有效三角形
    • for循环的参数遇到continue会+1；
    • 固定特殊值，第三条边
js
/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function (nums) {
    nums.sort((a, b) => a - b);
    let ans = 0;
    let n = nums.length;
    
    for (let m = n - 1; m >= 2; m--) {  // 固定最大边
        let l = 0;
        let r = m - 1;
        
        while (l < r) {
            let sum = nums[l] + nums[r];
            if (sum > nums[m]) {
                ans += r - l;  // 关键改动：一次性加所有可能的l
                r--;
            } else {
                l++;
            }
        }
    }
    return ans;
};