Study Notes

Appearance

灵神算法 · 01–08 整合（草稿） ​

由 灵神算法 文件夹下 01–08 号文件合并；便于通读与检索。

01 相向双指针（一） ​

源文件：01-相向双指针（一）.md

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

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

  • 如何得到思路：用坐标系把有序数组标记出来，把样例或自己造的数据在图上呈现，思考如何用代码得到正确答案。
  • 用 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;
};

02 相向双指针（二） ​

源文件：02-相向双指针（二）.md

来源：基础算法精讲 by 灵茶山艾府

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

题目代码备注
11. 盛最多水的容器代码
42. 接雨水代码额外讲了前后缀分解
125. 验证回文串代码*课后作业
2105. 给植物浇水 II代码*课后作业

例题 ​

盛最多水的容器 ​
  • 相向双指针，选两端计算面积
  • 木桶效应：每次移动较矮的一边，因为移动高的不可能让面积变大
  • 相等时移动哪边都可以（这里选择 r--）
js
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    //选两端，木桶原理，移动矮的找更大的；
    //相向双指针
    //不知道怎么处理相等的情况
    let l = 0, r = height.length -1;
    let ans = 0, minh = 0;
    while(l < r){
        minh = Math.min(height[l],height[r]);
        ans = Math.max(ans,(r-l)*minh)
        if (height[l] ===  height[r]) r--;
        else if(height[l] > height[r]) r--;
        else l++;
    }
    return ans;
};

时间复杂度：O(n)，空间复杂度：O(1)

接雨水 - 前后缀分解 ​
  • 每个位置能接的雨水 = min(左边最大值, 右边最大值) - 当前高度
  • 预处理两个数组：preMax[i] 前缀最大值，suffMax[i] 后缀最大值
  • 最后遍历一次累加每个位置的雨水量
js
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    // 根据例题发现，每次计算雨水格子，需要左边的最大值，右边的最大值，与当前值，所以需要维护两个数组
    //注意前缀和的生成
    let l = 0, n = height.length;
    let preMax = Array(n)
    let suffMax = Array(n)
    preMax[0] = height[0];
    suffMax[n - 1] = height[n - 1];
    for (let i = 1; i < n; i++) {
        preMax[i] = Math.max(height[i], preMax[i - 1])
    }

    for (let i = n - 2; i >= 0; i--) {
        suffMax[i] = Math.max(height[i], suffMax[i+1])
    }

    let ans = 0;
    for (let i = 0; i < n; i++) {
        ans += Math.min(preMax[i], suffMax[i]) - height[i];
    }

    return ans;
};

时间复杂度：O(n)，空间复杂度：O(n)（两个辅助数组）

接雨水 - 双指针 ​
  • 木桶原理的延伸：维护 preMax 和 suffMax，哪边小就处理哪边
  • 用指针移动 + 取最大值来动态维护前后最大值，省去辅助数组
  • 多画图模拟，多测试
js
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    //双指针的话，原理也是木桶，找到最小的一方计算那一方的ans
    //不知道怎么维护前后的最大值？还是比较呗，
    //指针+取最大，来维护前后最大值；
    let ans = 0, l = 0, r = height.length - 1, preMax = height[0], suffMax = height[r];

    while (l < r) {
        if (height[l] < height[r]) {
            ans += preMax - height[l++];
            preMax = Math.max(preMax, height[l])
        }
        else {
            ans += suffMax - height[r--];
            suffMax = Math.max(suffMax, height[r])
        }
    }
    return ans;
};

时间复杂度：O(n)，空间复杂度：O(1)（相比前后缀分解优化了空间）

作业题 ​

验证回文串 ​
  • 先过滤非字母数字字符，再用双指针从两端向中间比较
  • 正则 /[a-zA-Z0-9]/ 判断是否为合法字符
  • toLowerCase() 统一大小写后比较
js
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
    //toLowerCase,
    //正反l,r
    //不能直接剔除？
    const n = s.length;

    let reg = /[a-zA-Z0-9]/;
    let ss = "";
    // 使用正则表达式一次性过滤并转为小写
    // const filtered = s.toLowerCase().replace(/[^a-z0-9]/g, '');
    for (let i = 0; i < n; i++) {
        if (reg.test(s[i])) ss += s[i];
    }
    // 添加空字符串检查
    if (ss.length === 0) return true;
    let l = 0, r = ss.length - 1;
    while (l < r) {
        if (ss[l].toLowerCase() !== ss[r].toLowerCase()) {
            return false;
        }
        l++;
        r--;
    }
    return true;
};

时间复杂度：O(n)，空间复杂度：O(n)（构建了过滤后的字符串）

给植物浇水 II ​
  • 相向双指针模拟：Alice 从左、Bob 从右同时浇水
  • 水不够时补满再浇（注意是加满，不是累加剩余）
  • 踩坑：l === r 时需要单独判断谁来浇（优先 Alice，再 Bob，都不够就补水）
  • 核心调试思维：跟踪"状态变化"——什么变了、怎么变的、变之前还是变之后用旧值
js
/**
 * @param {number[]} plants
 * @param {number} capacityA
 * @param {number} capacityB
 * @return {number}
 */
var minimumRefill = function (plants, capacityA, capacityB) {
    //很明显的相向双指针了，要标记容量，模拟即可
    let ca = capacityA, cb = capacityB;
    let l = 0, r = plants.length - 1;

    let ans = 0;
    while (l < r) {
        if (ca >= plants[l]) ca -= plants[l++];
        else {
            ans++;
            //注意这里是加满，前面剩的不累加
            ca = capacityA - plants[l]
            l++;
        }
        if (cb >= plants[r]) cb -= plants[r--];
        else {
            ans++;
            cb = capacityB - plants[r]
            r--;
        }
        if (l === r) {
            if (ca >= plants[l]) break;
            else if (cb >= plants[l]) break;
            else ans++;
        }
        //可以优化成满足条件++；
    }
    return ans;
};

时间复杂度：O(n)，空间复杂度：O(1)

附录 ​

正则表达式基础 ​
1. 字符组 [] ​

方括号表示匹配其中的任意一个字符：

  • [abc] - 匹配 a、b 或 c 中的任意一个
  • [a-z] - 匹配任意小写字母（a 到 z）
  • [0-9] - 匹配任意数字（0 到 9）
  • [a-zA-Z] - 匹配任意大小写字母
2. 反向字符组 [^] ​

在方括号内开头使用 ^ 表示取反，匹配不在括号内的字符：

  • [^a-z] - 匹配任何不是小写字母的字符
  • [^0-9] - 匹配任何不是数字的字符
  • [^a-zA-Z0-9] - 匹配任何不是字母和数字的字符
3. 量词 + ​
  • + 表示前面的模式出现一次或多次
  • 例如：/a+/ 可以匹配 "a"、"aa"、"aaa" 等
4. 修饰符 g 和 i ​
  • g 表示全局匹配，不只是匹配第一个
  • i 表示忽略大小写
js
/abc/.test('ABC');   // false（区分大小写）
/abc/i.test('ABC');  // true（忽略大小写）

const str = 'a1b2c3';
str.match(/\d/);     // ["1"]（只找第一个数字）
str.match(/\d/g);    // ["1","2","3"]（找所有数字）
5. 分解 /[^a-z0-9]/g ​
js
/[^a-z0-9]/g

// 分解：
/           // 正则表达式的开始
[^          // 匹配任何不在以下字符组中的字符
a-z         // 小写字母 a 到 z
0-9         // 数字 0 到 9
]           // 字符组结束
/           // 正则表达式结束
g           // 全局匹配修饰符
6. 实际应用 ​
js
const s = "A man, a plan, a canal: Panama";

// 先转小写，再用正则替换
const filtered = s.toLowerCase().replace(/[^a-z0-9]/g, '');
// "amanaplanacanalpanama"
js
// 只保留数字
"abc123def456".replace(/[^0-9]/g, '');     // "123456"

// 只保留字母
"abc123def456".replace(/[^a-zA-Z]/g, '');  // "abcdef"

// 只保留中文
"Hello 你好 123".replace(/[^\u4e00-\u9fa5]/g, '');  // "你好"

// 移除所有空格
" a b c ".replace(/\s/g, '');              // "abc"

// 检查是否只包含字母数字
/^[a-zA-Z0-9]+$/.test("abc123");           // true
/^[a-zA-Z0-9]+$/.test("abc 123");          // false（包含空格）

// 提取所有单词
"Hello, world! 123".match(/[a-zA-Z]+/g);   // ["Hello", "world"]
常用正则速查表 ​
模式含义
\d数字，等价于 [0-9]
\D非数字，等价于 [^0-9]
\w单词字符（字母、数字、下划线），等价于 [a-zA-Z0-9_]
\W非单词字符
\s空白字符（空格、制表符等）
\S非空白字符
.匹配除换行符外的任意字符
js
// 用 \d 简化
"abc123".replace(/\D/g, '');    // "123"（保留数字）
"abc123".replace(/\d/g, '');    // "abc"（移除数字）

// 用 \w 简化
"hello_world!@#".replace(/\W/g, '');  // "hello_world"

03 滑动窗口 ​

源文件：03-滑动窗口.md

灵神视频精讲：滑动窗口

题单 ​

题目代码备注
209. 长度最小的子数组代码最短
3. 无重复字符的最长子串代码最长
713. 乘积小于 K 的子数组代码方案数
3090. 每个字符最多出现两次的最长子字符串代码*课后作业
2958. 最多 K 个重复元素的最长子数组代码*课后作业
2730. 找到最长的半重复子字符串代码*课后作业
2779. 数组的最大美丽值代码*课后作业
1004. 最大连续 1 的个数 III代码*课后作业
2962. 统计最大元素出现至少 K 次的子数组代码*课后作业
2302. 统计得分小于 K 的子数组数目代码*课后作业
1658. 将 x 减到 0 的最小操作数代码*课后作业
1234. 替换子串得到平衡字符串代码*课后作业
3795. 不同元素和至少为 K 的最短子数组长度代码*课后作业
76. 最小覆盖子串代码*课后作业

例题 ​

209. 长度最小的子数组 ​
  • 核心思路：同向双指针（滑动窗口）。
  • 模板：先移动右指针 r，当满足条件时（sum >= target），尝试移动左指针 l 缩小窗口，并更新答案。
  • 注意：打日志调试很重要。
js
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
    //明显不能从两端相向，应该是同向
    //if -> while打日志发现的；
    //滑窗模版
    let l = 0, r = 0, ans = Infinity, n = nums.length,sum = 0;
    if (n < 2) {
        if (nums[0] >= target) return 1;
    }

    while (r < n) {
        sum += nums[r];
        while(sum >= target) {
            console.log('l=',l,'r=',r,sum)
            ans = Math.min(ans,r - l +1)
            sum -= nums[l];
            l++;
        }
        r++;
        
    }
    return ans === Infinity ? 0 : ans;

};
3. 无重复字符的最长子串 ​
  • 数据结构：使用 Map 记录字符频率（或下标）。
  • 思路：
    • 右指针 r 向右移动，将字符加入窗口。
    • 如果窗口内有重复字符（mp.get(c) > 1），左指针 l 向右移动直到无重复。
    • 每次移动右指针后更新最大长度 ans。
  • 语法：?? 空值合并运算符（见附录）。
js
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    //涉及到数组or哈希map，js的哈希map没学过的:new Map(),set,get
    //滑动窗口（同向双指针）：答案更新一般靠近中后

    //知识点 x？？y，问号左边为null或undefined就用y；
    
    //如果没有就右边指针往右移动，如果有就左指针往右，要记录最长的长度而且无重复map[r];while 操作左指针可以去重
    let ans = 0, l = 0;
    const n = s.length;

    let mp = new Map();
    for (let r = 0; r < n; r++) {
        let c = s[r];
        // mp.set('c', 1);
        mp.set(c, (mp.get(c) ?? 0) + 1)
        while (mp.get(c) > 1) {
            mp.set(s[l], (mp.get(s[l]) ?? 0) - 1)
            l++;
        }
        // console.log(l, mp.get(s[l]), r, mp.get(s[r]))
        ans = Math.max(ans, r - l + 1)
    }
    return ans;
};
713. 乘积小于 K 的子数组 ​
  • 特征：窗口越大乘积越大（越不合法），窗口越小乘积越小（越合法）。
  • 思路：
    • 右指针扩大窗口，累乘。
    • 当乘积 >= k 时，左指针缩小窗口。
    • 关键：每次右指针固定时，合法子数组个数为 r - l + 1（避免双重循环）。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function (nums, k) {
    //由于连续，所以不能排序，大概率也不是相向双指针，看样例
    //判断答案就一个sum+if，关键是怎么遍历所有情况，先考虑滑动窗口，由于子数组越长，乘积越大，越不能满足题目要求；反之，子数组越短，乘积越小，越能满足题目要求。有这种性质的题目，可以用滑动窗口解决。


    //为什么滑动窗口可以遍历所有连续子数组？
    //固定右边，移动左边就可以用r-l+1来避免双重循环了
    let ans = 0, n = nums.length, ji = 1, l = 0;
    for (let r = 0; r < n; r++) {
        ji *= nums[r];
        while (ji >= k) {
            //写缩小逻辑
            ji /= nums[l];
            l++;
        }
        if (ji < k && l <= r) ans += r - l + 1;


    }
    return ans;
};

作业 ​

3090. 每个字符最多出现两次的最长子字符串 ​
  • 思路：同向双指针。右指针扩大窗口，Map 统计频次，当频次 > 2 时左指针缩小窗口。
  • 注意：Map 的 set 和 get 语法。
js
/**
 * @param {string} s
 * @return {number}
 */
var maximumLengthSubstring = function(s) {
    //要求最长，越大越合法，所以同向双指针，也就是滑动窗口
    //纯小写的话，直接插入map就行了
    //思路：右指针从左开始扩大窗口，while循环缩小不合法的窗口，更新答案
    let l = 0, n = s.length, ans = 0;
    let mp = new Map();
    for(let r = 0; r < n; r++){
        mp.set(s[r],(mp.get(s[r])??0)+1);

        while(mp.get(s[r])>2){
            mp.set(s[l],mp.get(s[l])-1);
            l++;
            // console.log(mp.get(s[r]),l,r)
        }
        ans = Math.max(ans,r - l +1)
    }
    return ans;
};
2958. 最多 K 个重复元素的最长子数组 ​

同上题，改两个变量名就行了

2730. 找到最长的半重复子字符串 ​
  • 思路：统计相邻相同字符的对数 cnt。
  • 缩小条件：当 cnt > 1 时，移动左指针，如果左指针移出的是一对重复字符，则 cnt--。
js
/**
 * @param {string} s
 * @return {number}
 */
var longestSemiRepetitiveSubstring = function (s) {

    //要求最长，越大越合法，所以同向双指针，也就是滑动窗口
    //为什么要r从1开始？：经验？
    let l = 0, n = s.length, cnt = 0, ans = 0;
    if (n === 1) return 1;
    for (let r = 1; r < n; r++) {
        if (s[r] === s[r - 1]) cnt++;
        if (n === 2 && cnt === 1) cnt = 0;
        while (cnt > 1) {
            if (s[l] === s[l + 1]) cnt--;

            l++;
            // console.log(mp.get(s[r]),l,r)

        }
        if (cnt <= 1) ans = Math.max(ans, r - l + 1);

    }
    return ans;
};
2779. 数组的最大美丽值 ​
  • 思路：
    • 排序：因为是选子序列（或理解为元素值调整），顺序不影响，先排序。
    • 转换：题目等价于找一个最长的子数组，使得 max - min <= 2*k。
    • 滑窗：nums[r] - nums[l] > 2*k 时缩小窗口。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumBeauty = function (nums, k) {
    //由于可以操作任意次，那可以排序
    nums.sort((a, b) => a - b);
    //越大越合法，滑动窗口
    //数学推导，带范围的可以在图上画好区间，发现要求的就是最多交集个数，也就是左边+k大于等于右边-k，那就用到反面条件来缩小窗口
    let ans = 0, l = 0, n = nums.length;
    for (let r = 0; r < n; r++) {

        // console.log('r - l', nums[r] - nums[l])
        while (nums[r] - nums[l] > 2 * k) {
            l++;
        }
        //合法的时候记录最大的
        ans = Math.max(ans, r - l + 1);
        // console.log(l, r, ans)
    }
    return ans;
};
1004. 最大连续 1 的个数 III ​
  • 思路：统计窗口内 0 的个数。
  • 条件：当 0 的个数 > k 时，缩小窗口。
  • 感悟：很有成就感的一题，多总结题目特征和调试经验。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
    //越大越合法，所以考虑相向双指针
    //要统计频次，哈希数组
    //缩小窗口的条件：0的次数大于k
    //在哪里打印？哪里变了？l,r,mp
    let l = 0, ans = 0, n = nums.length;
    let mp = new Map();
    for (let r = 0; r < n; r++) {
        mp.set(nums[r], (mp.get(nums[r]) ?? 0) + 1)
        while (mp.get(0) > k) {
            mp.set(nums[l], (mp.get(nums[r]) ?? 0) - 1);
            l++;
            // console.log('进循环了')
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
};
2962. 统计最大元素出现至少 K 次的子数组 ​
  • 思路：
    • 统计最大元素出现的次数 cnt。
    • 当 cnt === k 时，窗口合法。
    • 关键：当窗口 [l, r] 合法时，l 左边的所有位置作为左端点也都合法，所以 ans += l（注意这里代码逻辑是 while 循环结束后 l 指向的位置）。
    • 这里的代码逻辑是：当窗口内最大元素个数达到 k 时，尝试移动左指针，直到个数不足 k。每次移动左指针，说明找到了一个合法的左边界。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countSubarrays = function (nums, k) {
    //越大越合法，滑动窗口
    //难点：不知道缩小窗口的条件，不知道答案怎么计算
    //把方法和思路记住吧：在刚好合法的时候缩小到刚好不合法，那么此时l左边至少有一个max element，然后r指针指着一个，那（0，l-1）都是答案
    let ans = 0, l = 0, cnt = 0, maxelement = Math.max(...nums);
    for (let r = 0; r < nums.length; r++) {
        if (nums[r] === maxelement) cnt++;
        while (cnt === k) {
            if (nums[l] === maxelement) cnt--;
            l++;
        }
        ans += l;
    }
    return ans;
};
2302. 统计得分小于 K 的子数组数目 困难 ​
  • 特征：越短越合法。
  • 思路：
    • 维护窗口和 sum。
    • 当 sum * (r - l + 1) >= k 时（不合法），缩小窗口。
    • 合法时，以 r 为右端点的合法子数组个数为 r - l + 1。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countSubarrays = function (nums, k) {
    //容易想到，长度可以关联成r - l + 1;
    //要统计和那就移动右指针，貌似跟昨天的题很像，左指针往左的，不对
    //越小越合法？但是相向双指针就无法求和，还是滑窗？
    //暴力？一个一个加，< k/r-l+1，ans++,数据量太大肯定超时
    //看答案：越短越合法某一子数组合法那它的子数组也就都合法，所以只需要找一个缩小窗口的条件，找一下左右指针跟答案的关系
    //正常判断缩小条件，发现答案规律就是刚好缩小到合法之后的区间值

    let ans = 0, l = 0, sum = 0;
    for (let r = 0; r < nums.length; r++) {
        sum += nums[r];
        while (sum * (r - l + 1) >= k) {
            sum -= nums[l];
            l++;
        }
        // console.log(l,r)
        ans += r - l + 1;
    }
    return ans;
};
1658. 将 x 减到 0 的最小操作数 ​
  • 逆向思维：
    • 原问题：找两端子数组和为 x。
    • 转化后：找中间最长连续子数组，和为 sum - x。
  • 思路：标准滑动窗口找和为 target 的最长子数组。
js
/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var minOperations = function (nums, x) {
    //逆向思考，发现其实是，首尾相接，找最短数组让它之和🟰x，返回窗口长度
    //按照例题找出答案的规律试试，两个数组拼在一块，但是就是无法排除在数组中间部分而且长度很小的情况
    //越小越合法？靠在两边的滑动窗口？？？？
    //贪心？

    //原来是这样做的，在这个答案部分逆向：我们可以这样转化问题：
    // 设数组总和为 sum
    // 如果我们从两端取的总和为 x，那么中间剩余部分的和就是 sum - x
    // 问题转化为：找到最长的连续子数组，其和等于 sum - x
    // 那么最小操作数 = 总长度 -  .最长. 中间子数组长度
    // 这个转化很巧妙，因为找中间连续子数组比直接找两端子数组更容易！
    let ans = -1, l = 0;
    let sum = nums.reduce((a, b) => { return a + b }), tmp = sum - x, tmpsum = 0, n = nums.length;
    //     // 正确使用 reduce 计算数组总和（必须传回调函数）
    // const sum = nums.reduce((accumulator, currentValue) => {
    //   // accumulator：累计值（上一轮的结果），currentValue：当前遍历的元素
    //   return accumulator + currentValue;
    // }, 0); // 第二个参数 0 是初始值（推荐必传，避免空数组报错）

    for (let r = 0; r < nums.length; r++) {
        tmpsum += nums[r];

        while (tmpsum > tmp) {
            tmpsum -= nums[l];
            l++;
            // console.log(tmpsum, l, r)
        }
        if (tmpsum === tmp) {
            // console.log('循环外', l, r);
            ans = Math.max(ans, r - l + 1);
        }


    }
    return ans === -1 ? -1 : n - ans;
};
1234. 替换子串得到平衡字符串 困难 ​
  • 逆向思维：
    • 不要想“改什么”，要想“不改什么（保留什么）”。
    • 目标：保留下来的外部字符，每种字符数量都 <= n/4。
    • 这样剩下的空缺就可以通过替换子串来补齐。
  • 思路：统计频次，寻找最短子串，使得移除该子串后，剩余字符频次满足条件。
js
/**
 * @param {string} s
 * @return {number}
 */
var balancedString = function (s) {
    //又是越小越合法，但是，中间的变量明显不好搞，估计不是从窗口的反面考虑
    //越小越合法，还要连续子串，还要统计频次？？，不会做
    // 正确的逆向思路是：
    // 我们不要去想“要改什么”，而是去想“不改什么”。
    // 目标：最终整个字符串里，每个字符（Q, W, E, R）的数量都恰好是 n / 4。
    // 约束：我们只能通过替换一个连续子串来改变字符。这意味着，我们无法改变这个子串之外的字符。
    // 关键推论：既然子串之外的字符不能改，那么这些“外部”字符的数量，必须已经满足要求——也就是每种字符的个数都 不能超过 n / 4。
    // 为什么？ 因为如果外面某个字符（比如 Q）已经超过了 n / 4 个（比如有 3 个，而 n / 4=2），那这个 Q 就太多了。我们只能改子串里的字符，动不了外面的 Q，所以永远无法把多出来的 Q 减少，最终字符串一定不平衡。
    // 反过来说：只要外面每种字符的数量都不超过 n / 4，那么我们就可以通过巧妙地替换子串里的字符，来补齐那些数量不足的字符，让整个字符串达成平衡。
    // 所以，问题神奇地转化为了：寻找一个最短的连续子串，使得去掉这个子串后（即这个子串之外的字符），每种字符的数量都不超过 n / 4。

    //统计频次，寻找一个小点的窗口让外部都小于n/4，缩小窗口条件也就是外部各个频次都小于这个值
    const cnt = { Q: 0, W: 0, E: 0, R: 0 };
    const n = s.length, m = n / 4;
    let ans = n, l = 0;
    for (let x of s) {
        // cnt.x++;///x是值，不能这样写了
        cnt[x]++;
    }

    if (cnt.Q === m && cnt.E === m && cnt.W === m && cnt.R === m) return 0;
    for (let r = 0; r < n; r++) {
        cnt[s[r]]--;
        while (cnt.Q <= m && cnt.E <= m && cnt.W <= m && cnt.R <= m) {
            ans = Math.min(ans, r - l + 1)
            // console.log('in while', l, r)
            cnt[s[l]]++;
            l++;

        }

    }
    return ans === n ? 0 : ans;
};
3795. 不同元素和至少为 K 的最短子数组长度 ​
  • 思路：
    • 统计“有效元素”（频次为 1 的元素）的和。
    • 移动右指针，更新 Map 和 Sum。
    • 移动左指针缩小窗口时，注意 Sum 的更新时机（只有当元素频次减为 0 时，才从 Sum 中减去，这取决于题目对“不同元素和”的定义）。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minLength = function (nums, k) {
    //越小越合法，统计用于计算的频次最多1，他们之和要大于等于k，答案是这样的最小窗口长度
    //标志变量来标记是否使用呗？
    let ans = 1e5, l = 0, n = nums.length, sum = 0;
    let map = new Map();
    for (let r = 0; r < n; r++) {
        map.set(nums[r], (map.get(nums[r]) ?? 0) + 1);
        if (map.get(nums[r]) === 1) sum += nums[r];
        while (sum >= k && l <= r) {
            ans = Math.min(r - l + 1, ans)
            map.set(nums[l], (map.get(nums[l]) ?? 0) - 1);

            //主要是这一行，缩小sum的时机，因为统计nums【r】的时候，加入 ,c , c, b, r指针;两个c，算和是算了一次但是计频次记了两次，下次就是这种情况可以打印一下频次来排错
            if (map.get(nums[l]) === 0) sum -= nums[l];
            l++;
            // console.log('in while', l, r, sum, ans)
        }
    }
    return ans === 1e5 ? -1 : ans;

};
76. 最小覆盖子串 困难 ​
  • 核心：如何判断“涵盖”？
  • 技巧：使用 Array(128) 和 codePointAt(0) 代替 Map 提高性能。
  • 思路：
    • 统计 t 中字符频次。
    • 移动右指针，统计窗口内字符频次。
    • check 函数检查是否涵盖。
    • 涵盖时，尝试移动左指针缩小窗口，并记录最小长度。
js
function isCovered(cntS, cntT) {
    //优先判断false的情况
    for (let i = 'A'.codePointAt(0); i <= 'Z'.codePointAt(0); i++) {
        if (cntS[i] < cntT[i]) {
            return false;
        }
    }
    for (let i = 'a'.codePointAt(0); i <= 'z'.codePointAt(0); i++) {
        if (cntS[i] < cntT[i]) {
            return false;
        }
    }
    return true;
}

var minWindow = function(s, t) {
    const cntS = Array(128).fill(0); 
    const cntT = Array(128).fill(0);
    for (const c of t) {
        cntT[c.codePointAt(0)]++;
    }

    const m = s.length;
    let ansLeft = -1, ansRight = m,left = 0;

    for (let right = 0; right < m; right++) {
        cntS[s[right].codePointAt(0)]++; // 右端点字母移入子串
        while (isCovered(cntS, cntT)) { // 涵盖
            if (right - left < ansRight - ansLeft) { // 找到更短的子串
                ansLeft = left; // 记录此时的左右端点
                ansRight = right;
            }
            cntS[s[left].codePointAt(0)]--; // 左端点字母移出子串
            left++;
        }
    }

    return ansLeft < 0 ? "" : s.substring(ansLeft, ansRight + 1);
};

附录 ​

1. JavaScript Map 基础 ​

在刷题中，推荐使用 Map 而不是普通对象，因为 Map 在频繁增删键值对时性能更好，且键可以是任意类型。

常用操作：

javascript
const map = new Map();
// 增/改
map.set('key', 1);
// 查
map.get('key'); // 返回 1
map.has('key'); // 返回 true
// 删
map.delete('key');
// 默认值技巧
let val = map.get(key) ?? 0; // 如果不存在则为 0
2. 空值合并运算符 (??) ​

?? 专门用于处理 null 和 undefined。

javascript
// 刷题常用写法：获取 map 值，如果不存在则默认为 0
mp.set(c, (mp.get(c) ?? 0) + 1);
3. 对象属性的引号 ​
  • 不加引号：属性名符合标识符规则（字母开头，无特殊字符）。
    js
    const count = { Q: 0, W: 0 };
  • 动态访问：必须使用 []。
    js
    const key = 'Q';
count[key]++; // 正确
// count.key++ // 错误：这会找名为 "key" 的属性
4. 字符编码操作 ​

对于 ASCII 字符统计（如大小写字母），使用数组比 Map 更快。

  • codePointAt(0)：获取字符的 Unicode 码点（ASCII 码）。
    js
    'A'.codePointAt(0); // 65
  • Array(128).fill(0)：创建一个长度 128 的数组并初始化为 0，足以覆盖所有 ASCII 字符。

04 二分查找 ​

源文件：04-二分查找.md

来源：基础算法精讲 by 灵茶山艾府

视频精讲：二分查找

题目代码备注
34. 在排序数组中查找元素的第一个和最后一个位置代码三种写法
2529. 正整数和负整数的最大计数代码*课后作业
2300. 咒语和药水的成功对数代码*课后作业
1385. 两个数组间的距离值代码*课后作业
2080. 区间内查询数字的频率代码*课后作业
2563. 统计公平数对的数目代码*课后作业
875. 爱吃香蕉的珂珂代码*课后作业
2187. 完成旅途的最少时间代码*课后作业
275. H 指数 II代码*课后作业
2861. 最大合金数代码*课后作业
2439. 最小化数组中的最大值代码*课后作业
2517. 礼盒的最大甜蜜度代码*课后作业

例题 ​

在排序数组中查找元素的第一个和最后一个位置 ​
  • 推荐开区间写法，循环不变量贯穿始终
  • 初始化 l = -1, r = nums.length，(l, r) 表示开区间，两个端点明确不是答案
  • 循环条件 l + 1 < r：当 l + 1 === r 时区间内无元素，停止循环
  • nums[mid] >= target → 收缩 r = mid（第一个 >= target 的位置可能在 mid 或更左，包含 mid 本身）
  • nums[mid] < target → 收缩 l = mid（mid 及左边都 < target，答案在右边）
  • 循环结束后 l 和 r 相邻，r 就是第一个 >= target 的下标（即 lowerbound）
  • 由于索引从 0 开始，偶数长度时 mid 视觉上偏左
js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var lowerbound = function (nums, target) {
  let l = -1,
    r = nums.length;
  //要移动指针缩小范围，就要判断target跟中间值的大小
  //由于初始化两个开区间，那么循环条件就是r - l > 1？？不太懂对不对
  while (l + 1 < r) {
    const mid = Math.floor((l + r) / 2);
    //目标值在中间值左边，收缩右边指针，但是可能有连续的目标值，所以要有等于号
    if (nums[mid] >= target) r = mid;
    //相反
    else l = mid;
  }
  //循环结束之后，l跟r挨着，第一个target是r
  return r;
};
var searchRange = function (nums, target) {
  const start = lowerbound(nums, target);

  const end = lowerbound(nums, target + 0.5) - 1;
  //怎么，判断有没有取到正确答案？记住
  if (start === nums.length || nums[start] !== target) {
    return [-1, -1]; // nums 中没有 target
  }

  return [start, end];
};

时间复杂度：O(log n)，空间复杂度：O(1)

作业题 ​

正整数和负整数的最大计数 ​

略

咒语和药水的成功对数 ​
  • 排序 potions 后对每个 spell 二分查找，抓住有序特征
  • 条件转化：spells[i] * potions[j] >= success → potions[j] >= ceil(success / spells[i])
  • 为什么取 ceil：假如得到 3.4，用 3 就多了错误答案，4 刚刚好
  • 踩坑：JS 箭头函数有花括号就要有 return
js
/**
 * @param {number[]} spells
 * @param {number[]} potions
 * @param {number} success
 * @return {number[]}
 */

var lowerbound = function (nums, target) {
    //开区间比较形象
    let l = -1, r = nums.length;
    //循环不变量：区间大于1，先找大于等于的
    while (l + 1 < r) {
        //注意，这里不必这样写，是cpp和java可能溢出，这里别忘记去除小数，下标必须是整数
        let mid = Math.floor(l + (r - l) / 2);

        if (nums[mid] >= target) r = mid;
        else l = mid;
    }
    return r;
}
var successfulPairs = function (spells, potions, success) {
    let m = spells.length, n = potions.length;
    let tmp,index, ans = [];
    //有花括号就要有return！！！
    potions.sort((a,b)=>a-b);
    // 要想应用二分查找，要抓住有序的特征，所以spells[m] * potions[n] >= 7;
    //变成了 potions[n] >= floor(7/ spells[m]),为什么取ceil，因为假如得到3.4,用3就多了错误答案，4刚刚好
    for(let i = 0; i < m; i++){
        tmp = Math.ceil(success/spells[i]);

        index = n - lowerbound(potions,tmp);
        // console.log(i,index,tmp)
        // ans = [...ans,index];
        ans.push(index);
    }
    return ans;
};

时间复杂度：O((m + n) log n)，空间复杂度：O(1)（不计排序空间）

两个数组间的距离值 ​
  • 绝对值条件 |arr1[i] - arr2[j]| > d 等价于 arr2 中没有元素落在 [x-d, x+d] 范围内
  • 排序 arr2 后，用 lowerbound 找第一个 >= x - d 的元素，再检查它是否 <= x + d
  • 分步判断：先定位再验证，注意二分的返回值是下标
js
var findTheDistanceValue = function (arr1, arr2, d) {
    let ans = 0;
    arr2.sort((a, b) => a - b);
    
    for (let x of arr1) {
        // 找第一个 >= x-d 的元素
        let idx = lowerbound(arr2, x - d);
        
        // 检查这个元素是否在 [x-d, x+d] 范围内
        // 如果 idx 在数组范围内，并且 arr2[idx] <= x+d，说明区间内有元素
        if (idx < arr2.length && arr2[idx] <= x + d) {
            // 存在元素在区间内，x不符合条件
            continue;
        } else {
            // 区间内没有元素，x符合条件
            ans++;
        }
    }
    
    return ans;

时间复杂度：O((m + n) log n)，空间复杂度：O(1)（不计排序空间）

区间内查询数字的频率 ​
  • 频率查询 → 用 Map 记录每个值出现的所有下标，Map 的值是数组
  • 查询时对下标数组二分：找第一个 >= left 的位置和第一个 >= right + 1 的位置，差值即频率
  • JS 类定义：构造函数 + 原型方法
  • Map 常用 API：has（查键）、set(val, [])（插入数组为值）、get（取值）、数组的 push（追加元素）
js

// 构造函数（类似 C++ 的 RangeFreqQuery::RangeFreqQuery）
var RangeFreqQuery = function(arr) {
    // 在 JavaScript 中，this 指向新创建的对象
    // 相当于 C++ 的 this->indexMap
    this.indexMap = new Map();
    
    // 遍历数组，记录每个值的索引
    for (let i = 0; i < arr.length; i++) {
        const val = arr[i];
        if (!this.indexMap.has(val)) {
            this.indexMap.set(val, []);
        }
        this.indexMap.get(val).push(i);
    }
};



// 给原型添加 query 方法（类似 C++ 的成员函数）
RangeFreqQuery.prototype.query = function(left, right, value) {
    // 如果这个值从未出现过
    if (!this.indexMap.has(value)) {
        return 0;
    }
    
    const indices = this.indexMap.get(value);
    
    // 找第一个 >= left 的位置
    const leftIndex = lowerbound(indices, left);
    // 找第一个 > right 的位置（即第一个 >= right+1 的位置）
    const rightIndex = lowerbound(indices, right + 1);
    
    // 范围内索引的个数
    return rightIndex - leftIndex;
};

时间复杂度：构造 O(n)，查询 O(log n)；空间复杂度：O(n)

统计公平数对的数目 ​
  • 排序后对每个 nums[i]，在 [i+1, n-1] 范围内二分查找满足 lower <= nums[i] + nums[j] <= upper 的 j
  • 改造 lowerbound，多传入一个 start 参数保证不重复计数（j > i）
  • 踩坑：传 i+1 而非 i，否则 x 与 [x, y] 匹配会把自己也算进去，应该是 x 与 [x+1, y]
  • 虽然最终还是没搞出来，但已经接近得很了——读题 → 模拟样例 → 想办法用代码实现
js
/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */

//处理特殊情况，全是0
var countFairPairs = function (nums, lower, upper) {
    const n = nums.length;
    let ans = 0;

    nums.sort((a, b) => a - b);

    for (let i = 0; i < n; i++) {
        let tmpl = lower - nums[i], tmpr = upper - nums[i];
        //为什么要i+1，因为是当前值与后面的区间值匹配，如果是i，就比如,x与[x,y]匹配了，把自己也算了进去，应该是x与[x+1,y]
        if(i < n - 1) ans += lowerbound(nums, tmpr+1,i+1) - lowerbound(nums, tmpl,i+1);
        console.log('ans',ans)
    }
    return ans;

};


//多传入一个start参数保证不重复计数
var lowerbound = function (nums, target,start) {
    //开区间比较形象
    let l = start - 1, r = nums.length;
    //循环不变量：区间大于1，先找大于等于的
    while (l + 1 < r) {
        //注意，这里不必这样写，是cpp和java可能溢出，这里别忘记去除小数，下标必须是整数
        let mid = Math.floor(l + (r - l) / 2);

        if (nums[mid] >= target) r = mid;
        else l = mid;
    }
    return r;
}

时间复杂度：O(n log n)，空间复杂度：O(1)（不计排序空间）

爱吃香蕉的珂珂 ​
  • 二分答案：不是在数组下标上二分，而是在答案范围 [1, max(piles)] 上二分
  • 开区间的真正含义：left = 0（明确不可行，速度不能为 0）、right = max(piles)（明确可行，n 堆最多 n 小时吃完，题目保证 n ≤ h）
  • 合法条件 sum <= h（总时间不超限）→ 尝试更小速度 r = mid
  • 不合法 sum > h（超时）→ 需要提速 l = mid
js
/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */

//二分查找模版的变体而已，就是改了一下判断条件
//找最小，就是刚好大于等于
var minEatingSpeed = function (piles, h) {
    piles.sort((a, b) => a - b);
    let l = 0, r = Math.max(...piles);
    while (l + 1 < r) {
        let sum = 0;
        //求和，尝试找k，容易发现k的范围就是数组最小值和最大值之间
        let mid = Math.floor((l + r) / 2);

        for (const x of piles) {
            sum += Math.ceil(x / mid);
        }
        // console.log(mid, sum)
        //往左的时候，条件为,当前花的时间要大于规定时间，答案可能在。。。。。。哦不对，sum大于h，说明超时了，那要提升速度，mid要变大，所以要往右；
        // if (sum >= h ) r = mid;
        //所以花的时间小于规定时间（合法），那就尝试找更小的速度
        if (sum <= h) r = mid;
        ///不合法，花的时间sum大于h，那自然要提速度
        else l = mid;
    }

    return r;
};

时间复杂度：O(n log max(piles))，空间复杂度：O(1)

完成旅途的最少时间 ​
  • 二分答案：猜一个时间 mid，计算所有车在该时间内能完成的总旅程数
  • 左边界 l = min(time) - 1（最快的车至少需要 1 个单位时间），右边界 r = max(time) * totalTrips
  • sum >= totalTrips → 时间够用，尝试更少 r = mid；否则 l = mid
js
//最少时间，也就是找到t，得到的旅途数刚好大于等于target；
//二分猜测，猜4答案是t，计算旅程数
//注意，越快的车走的旅程数越多
var minimumTime = function (time, totalTrips) {

    //最少多少时间？按照速度最快的时间基准来
    //最多多少时间？就算速度最慢的，这个时间由次数乘以最大的单位时间
    let mint = Math.min(...time);
    //
    let l = mint - 1, r = Math.max(...time)*totalTrips;

    while (l + 1 < r) {
        let mid = Math.floor((l + r) / 2);
        let sum = 0;
        for(let x of time){
            sum += Math.floor(mid/x)
        }
        if (sum >= totalTrips) r = mid;
        else l = mid;
    }
    return r;
};

时间复杂度：O(n log(max(time) × totalTrips))，空间复杂度：O(1)

H 指数 II ​
  • 已排序数组，找第一个满足 citations[mid] >= n - mid 的位置
  • 考虑极端情况：最少 0 篇论文引用 0 次，最多 n 篇论文至少引用了 n 次
  • 开区间 l = -1, r = n，答案为 n - r
js

var hIndex = function (citations) {
    //考虑极端情况；最少1篇论文引用0次，最多n篇论文至少引用了n次；中间靠后h篇论文引用h次

    let n = citations.length;
    let l = - 1, r = n;

    while (l + 1 < r) {
        let mid = Math.floor((l + r) / 2);
        if (citations[mid] >= n - mid) r = mid;
        else l = mid;
    }
    return n - r;

};

时间复杂度：O(log n)，空间复杂度：O(1)

最大合金数 ​

不做了

最小化数组中的最大值 ​

不做了

礼盒的最大甜蜜度 ​
  • 最大化最小值 → 典型二分答案特征，排序后再尝试
  • 贪心验证：对于猜测的甜蜜度 d，从最小价格开始，每次选第一个与上一个差 >= d 的糖果
  • 如果能选出 >= k 个，说明 d 可行（left = mid）；否则 d 太大（right = mid）
  • 题目要返回的最大甜蜜度是一个差值，但验证时不是做差而是贪心逐个验证，思维转换在这和二分的结合点上
  • 需要一个 pre 变量记录上一个选中的糖果价格
模拟过程 ​

价格数组 price = [1, 2, 5, 8, 13, 21]，k = 3：

确定猜答案的范围：

  • 左边界 left = 0（最小间距）
  • 右边界 right = 20（最大价格 21 - 最小价格 1）

猜 d = 10：

  1. 先选 1
  2. 找 >= 1 + 10 = 11 → 选 13
  3. 找 >= 13 + 10 = 23 → 找不到

只选出 2 个 < k = 3，太大了，去左半边 [0, 9]。

猜 d = 7：

  1. 先选 1
  2. 找 >= 1 + 7 = 8 → 选 8
  3. 找 >= 8 + 7 = 15 → 选 21

选出 3 个 >= k，可行！甜蜜度为 7。（选出 (1, 8, 21)）

js
var maximumTastiness = function(price, k) {
    function f(d) {
        let cnt = 1, pre = price[0]; // 先选一个价格最小的糖果
        for (const p of price) {
            if (p - pre >= d) { // 可以选 p
                cnt++;
                pre = p;
            }
        }
        return cnt;
    }

    price.sort((a, b) => a - b);
    let left = 0;
    let right = Math.floor((price[price.length - 1] - price[0]) / (k - 1)) + 1;
    while (left + 1 < right) { // 开区间不为空
        // 循环不变量：
        // f(left) >= k
        // f(right) < k
        const mid = Math.floor((left + right) / 2);
        if (f(mid) >= k) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return left; // 最大的满足 f(left) >= k 的数
};

时间复杂度：O(n log((max - min) / (k - 1)))，空间复杂度：O(1)（不计排序空间）

为什么 f(d) >= k 就够了？ ​

如果贪心选出了 m 个糖果（m >= k），那么这 m 个糖果中任取 k 个，它们之间的最小差一定 >= d：

  • 贪心选出的 m 个糖果，每相邻两个的差都 >= d
  • 从中任取 k 个，跳过了中间的一些糖果，差只会更大
  • 所以这 k 个糖果也一定满足任意差 >= d
例子（d=5）：
选 1 (prev=1)
选 8 (8-1=7≥5) ✓
选 13 (13-8=5≥5) ✓
结果：差值 [7,5]，最小差=5 ≥ d ✅
贪心策略为什么能得到最多？ ​

命题：对于排序后的价格数组，每次都选第一个满足"与上一个差 >= d"的糖果，能得到最多的糖果数。

基础情况 — 第一个选最小的总是最优：

假设最优解第一个选的是 price[i] (i > 0)，把它替换成 price[0]：

  • price[0] <= price[i]
  • 起点更小，后面的糖果更容易满足差价条件
  • 替换后至少不会选得更少

归纳步骤 — 每次选第一个可行的是最优：

设第一个满足条件的糖果价格为 x，假设最优解选了价格为 y 的（y >= x）：

比较两种选择：
┌─────────────────────────────────────────┐
│ 贪心选 x                                 │
│ 后面可选的糖果：所有 ≥ x+d 的糖果         │
├─────────────────────────────────────────┤
│ 最优解选 y                                │
│ 后面可选的糖果：所有 ≥ y+d 的糖果         │
└─────────────────────────────────────────┘

因为 x ≤ y，所以 {糖果 ≥ y+d} ⊆ {糖果 ≥ x+d}
也就是说，选 x 后面的可选集合 ≥ 选 y 后面的可选集合

反例验证：

价格：[1, 3, 4, 6, 9]，d = 3

贪心：选 1 → 选 4 → 选 9 → [1,4,9] 共 3 个
跳过 4 选 6：选 1 → 选 6 → 选 9 → [1,6,9] 也是 3 个
跳过更多：选 1 → 选 9 → [1,9] 只有 2 个 ❌

跳过一个可行选择不会增加后续机会：
- 跳过的数 x 能满足条件
- 后面选的 y ≥ x
- 起点变大了，可选集合变小了
类比：活动选择问题 ​

这很像经典的"活动选择"问题：

  • 每个糖果看作一个"活动"，"开始时间"是价格
  • 条件 p - pre >= d 相当于两个活动之间必须有至少 d 的间隔
  • 贪心策略：每次选第一个满足间隔条件的（即当前可选中最小的）就是最优

附录 ​

开闭区间概述 ​

区间定义决定了边界值的含义：

  • 闭区间：left 和 right 都是当前可能包含答案的范围
  • 左闭右开：right 是第一个不满足条件的位置（或超出范围）
  • 开区间：left 是最后一个 < target 的位置，right 是第一个 >= target 的位置

循环条件随之变化：必须保证区间内至少有一个待检查的元素。

更新规则必须维持循环不变量：这是最核心的。只要你维护好不变量，最终答案就会落在预期的边界上。

mid 落在 target 索引的位置是否受影响？不，Math.floor((left+right)/2) 在所有实现中都是一样的，只是 left 和 right 的值不同，导致 mid 的取值序列可能不同。但最终搜索到的目标位置是相同的。mid 只是一个探针，帮助我们缩小范围。

为什么开区间写法可能更直观？

  • 左边界的左边所有元素 < target（且左边界本身 < target）
  • 右边界的右边所有元素 >= target（且右边界本身 >= target）
  • 每次比较 mid 后，根据结果将 mid 赋给左或右边界，区间始终保持开区间，且不变量自动维持
  • 循环结束时，左右边界相邻，此时右边界就是第一个 >= target 的位置
  • 不需要 ±1 操作，不容易出现边界错误，因此许多算法竞赛选手偏爱这种风格
为什么用 floor 而不是 ceil ​

核心原因：保持区间不变量的正确性。

假设数组 [1, 3, 5, 7, 9]，l = -1, r = 5：

js
mid = Math.floor((l + r) / 2) = Math.floor(4 / 2) = 2
// 得到中间偏左的位置，没问题

关键场景：当 l 和 r 相邻时（l + 1 = r）：

  • (l + r) / 2 = l + 0.5
  • floor 得到 l
  • ceil 得到 r

如果用 ceil：

js
while (l + 1 < r) {
    mid = Math.ceil((l + r) / 2);  // 当 l+1=r 时，mid = r
    
    if (nums[mid] >= target) {
        r = mid;  // r 不变（还是 r）
    } else {
        l = mid;  // l 变成 r
    }
    // 区间没缩小！可能死循环
}

用 floor 就安全：

js
while (l + 1 < r) {
    mid = Math.floor((l + r) / 2);  // 当 l+1=r 时，mid = l
    
    if (nums[mid] >= target) {
        r = mid;  // r 变成 l，区间缩小
    } else {
        l = mid;  // l 变成 l（不变？）
    }
    // 检查：如果 nums[l] < target，l 不变，但 r 会变
    // 无论如何，区间一定会缩小
}

偶数长度视觉化：

数组长度 6（偶数）：[10, 20, 30, 40, 50, 60]
下标：0   1   2   3   4   5

中间有两个值：下标 2(30) 和 3(40)
用 floor: (0+5)/2 = 2.5 → floor = 2 ✓ 取左边的中间值
用 ceil:  (0+5)/2 = 2.5 → ceil  = 3 ✗ 取右边的中间值

二分查找的标准实现都选 floor（左边），因为代码简单、避免边界死循环、符合编程直觉。

JS 数组方法 ​
js
let arr = [1, 2, 3];

arr.push(4);           // 末尾添加 → [1, 2, 3, 4]
arr.pop();             // 末尾删除 → [1, 2, 3]
arr.unshift(0);        // 开头添加 → [0, 1, 2, 3]
arr.shift();           // 开头删除 → [1, 2, 3]
方法是否创建新数组性能返回值
push否（修改原数组）高新数组长度
展开运算符 [...ans, count]是（创建新数组）较低新数组

循环中用 push 性能更好，不会每次创建新数组。

上下取整转换 ​

⌈a/b⌉ = ⌊(a-1)/b⌋ + 1（当 a, b 为正整数时）

为什么要做这个变换？ 避免浮点数精度问题，用整数运算代替浮点数运算。

js
// 直接上取整（刷题常用，99% 情况够用）
sum += Math.ceil(p / mid);

// 公式转换（避免浮点数精度问题，工程场景更稳）
sum += Math.floor((p - 1) / mid) + 1;

验证：

  • a=7, b=3: ⌈7/3⌉ = 3, ⌊6/3⌋+1 = 2+1 = 3 ✓
  • a=6, b=3: ⌈6/3⌉ = 2, ⌊5/3⌋+1 = 1+1 = 2 ✓
  • a=5, b=3: ⌈5/3⌉ = 2, ⌊4/3⌋+1 = 1+1 = 2 ✓

求和公式展开：把每个 ⌊(p-1)/k⌋+1 加起来 = sum(⌊(p-1)/k⌋) + n ≤ h，这是数学上的简化写法，对实际写代码没有太大帮助，但有助于理解数学本质。

结论：刷题直接用 Math.ceil(p/mid) 完全没问题，不影响二分查找的核心思想。

三种区间写法详解（以珂珂吃香蕉为例） ​
闭区间 [left, right] ​
js
function minEatingSpeed(piles, h) {
    let left = 1;      // 最小可能速度
    let right = Math.max(...piles);  // 最大可能速度
    
    while (left <= right) {  // [left, right] 不为空
        let mid = Math.floor((left + right) / 2);
        
        if (canFinish(piles, mid, h)) {
            right = mid - 1;  // mid 已经可行，试试更慢的
        } else {
            left = mid + 1;   // mid 不可行，需要更快的
        }
    }
    return left;  // 循环结束时，left 是第一个可行的
}
  • 初始：left=1（可行？未知），right=max（可行？未知）
  • 循环条件：left <= right 表示区间还有元素
  • 移动规则：排除 mid 后，区间缩小为 [left, mid-1] 或 [mid+1, right]
  • 结束时：left > right，left 就是答案
左闭右开 [left, right) ​
js
function minEatingSpeed(piles, h) {
    let left = 1;      // 最小可能速度
    let right = Math.max(...piles) + 1;  // 注意这里 +1
    
    while (left < right) {  // [left, right) 不为空
        let mid = Math.floor((left + right) / 2);
        
        if (canFinish(piles, mid, h)) {
            right = mid;     // mid 可行，把右边界拉过来
        } else {
            left = mid + 1;  // mid 不可行，排除后往右
        }
    }
    return left;  // 循环结束时，left == right 就是答案
}
  • 初始：left=1，right=max+1（right 本身不在区间内）
  • 循环条件：left < right 表示区间还有元素
  • 移动规则：right=mid 表示新的右边界（不包含 mid），left=mid+1 表示排除 mid
  • 结束时：left == right，这个值就是答案
开区间 (left, right) ​
js
function minEatingSpeed(piles, h) {
    let left = 0;      // 肯定不可行的
    let right = Math.max(...piles);  // 肯定可行的
    
    while (left + 1 < right) {  // (left, right) 不为空
        let mid = Math.floor((left + right) / 2);
        
        if (canFinish(piles, mid, h)) {
            right = mid;     // mid 可行，更新右边界
        } else {
            left = mid;      // mid 不可行，更新左边界
        }
    }
    return right;  // 循环结束时，right 是第一个可行的
}
  • 初始：left=0（明确不可行），right=max（明确可行）
  • 循环条件：left + 1 < right 表示中间还有元素
  • 移动规则：直接 left=mid 或 right=mid，不 +1/-1
  • 结束时：left 和 right 相邻，right 就是答案
对比表 ​
方面闭区间 [L,R]左闭右开 [L,R)开区间 (L,R)
左指针初始最小可能值最小可能值明确不可行的值
右指针初始最大可能值最大可能值+1明确可行的值
循环条件L ≤ RL < RL + 1 < R
可行时移动R = mid - 1R = midR = mid
不可行时移动L = mid + 1L = mid + 1L = mid
返回答案LLR

开区间写法最容易理解：左右边界有明确含义（不可行 vs 可行），移动指针不用想 ±1，循环结束时答案直接是 right。

05 二分查找 - 变形 ​

源文件：05-二分查找 - 变形.md

来源：基础算法精讲 by 灵茶山艾府

视频精讲：二分查找 - 变形

题目代码备注
162. 寻找峰值代码
153. 寻找旋转排序数组中的最小值代码
33. 搜索旋转排序数组代码两种方法
74. 搜索二维矩阵代码*课后作业
1901. 寻找峰值 II代码*课后作业
154. 寻找旋转排序数组中的最小值 II代码*课后作业

例题 ​

162.寻找峰值 ​

  • 这个题不能排序，但是却可以用二分，因为题目说如果有多个峰值随便找到一个就可以，而且相邻元素不会相同
js
/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function (nums) {
    //相邻的数都不同，假设，随便找一个，
    //样例模拟发现，如果r初始化在n-1，答案就小于等于nums[r]，答案大于[l]；；二分是大于l小于r
    let l = -1, n = nums.length;
    let r = n - 1;
    while (l + 1 < r) {
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] < nums[mid + 1]) {
            //ans may be in right;
            l = mid;
        }
        else r = mid
        // console.log(mid,l,r)
    }
    return r;

};

153.寻找旋转排序数组中的最小值 ​

  • 利用好有序这一性质，看成一个递增的线段，旋转就看成线段分成两部分重排序，有点像跳跃间断点？
js
var findMin = function(nums) {
    //利用好事先有序的特性，按照视频里的线段来可视化的分析中间值跟tail值大小情况
    let l = -1, n = nums.length;
    let r = n - 1;
    while (l + 1 < r) {
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] > nums[n-1]) {
            l = mid;
        }
        else r = mid
        // console.log(mid,l,r)
    }
    return nums[r];
};

33.搜索旋转排序数组 ​

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */


var search = function (nums, target) {
    let n = nums.length;
    const tail = nums[n-1];
    let minIndex = findMin(nums);

    if(target > tail){
        return lowerBound(nums,-1,minIndex,target);
    }

    return lowerBound(nums,minIndex - 1,n,target);
};
// 153. 寻找旋转排序数组中的最小值（返回的是下标）
var findMin = function (nums) {
    let left = -1, right = nums.length - 1; // 开区间 (-1, n-1)
    while (left + 1 < right) { // 开区间不为空
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] < nums[nums.length - 1]) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return right;
};

var lowerBound = function (nums, left, right, target) {
    while (left + 1 < right) { // 开区间不为空
        // 循环不变量：
        // nums[right] >= target
        // nums[left] < target
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] >= target) {
            right = mid; // 范围缩小到 (left, mid)
        } else {
            left = mid; // 范围缩小到 (mid, right)
        }
    }
    return nums[right] === target ? right : -1;
};

作业 ​

06 链表 - 反转系列 ​

源文件：06-链表 - 反转系列.md

来源：基础算法精讲 by 灵茶山艾府

题目代码备注
206. 反转链表代码
92. 反转链表 II代码
25. K 个一组翻转链表代码
24. 两两交换链表中的节点代码*课后作业
445. 两数相加 II代码*课后作业
2816. 翻倍以链表形式表示的数字代码*课后作业

例题 ​

206.反转链表 ​

  • 看注释的思考过程
js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    //每个节点都存了next属性，这是一个地址，在图片里其实就是箭头，反转链表就是反转箭头，
    //比如1，2，3，反转过程：1的next指到null,2的next值到1，3的next指到2；
    //每次切换指向，涉及到的变量有current，previous，但是curr还需要遍历，所以要提前保存curr.next,同时注意pre也需要跟随curr遍历
    //最终，curr指到null，pre值到原来的尾，稍微想一下能想象出来
    let curr = head;
    let pre = null;

    while(curr){
        let nxt = curr.next;

        curr.next = pre;

        pre = curr;
        curr = nxt;
    }
    return pre;
};

92.反转链表二 ​

  • 看懂报错，去思考为什么，注意特殊情况
  • 脑海里要有上一题反转链表的画面，清楚反转完的pre,curr,next指向哪里，多打印
js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
    //局部反转，先把局部聚焦，看成整条反转，回想整条反转最后的指针curr，pre的位置，
    //可以发现结束后curr位置需要被left位置节点的next指过去，pre位置要被left左边的指过去
    //所以，这个left左边需要记录一下这个节点，
    //通常称之为 哑节点/哨兵节点


    //virtual node
    const dummy = new ListNode(0, head);
    let p0 = dummy;
    for (let i = 0; i < left - 1; i++) {
        p0 = p0.next;
    }
    let pre = p0;
    curr = p0.next;
    // console.log('curr', curr)
    //反转
    for (let i = 0; i < right - left + 1; i++) {
        let nxt = curr.next;
        //下面报错意思是只有一个节点的时候，为空，所以要引入虚拟头节点
        // Line 28 in solution.js
        //         let nxt = curr.next;
        //                        ^
        // TypeError: Cannot read properties of null (reading 'next')
        //     Line 28: Char 24 in solution.js (reverseBetween)
        //     Line 56: Char 19 in solution.js (Object.<anonymous>)
        curr.next = pre;
        pre = curr;
        curr = nxt;
    }

    p0.next.next = curr;
    p0.next = pre;//left指到反转链表的尾

    // console.log(p0, dummy,pre, curr)
    //注意，p0最终是left左边一位，dummy.next才是整个完整答案
    return dummy.next
};

k个一组翻转链表 ​

  • 参考上两题和注释
  • 画图，一步一步来，这里的循环条件写法值得学习
  • 注意p0节点的更新思路
js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */

//k个一组进行反转，走一步看一步，pre，curr，nxt的位置，看起来是需要虚拟节点的

var reverseKGroup = function (head, k) {
    //统计节点个数技巧
    let n = 0;
    for (let tmp = head; tmp != null; tmp = tmp.next) n++;
    console.log('count', n)

    //v node
    const dummy = new ListNode(0, head);

    let p0 = dummy, pre = null, curr = head;

    for (; n >= k; n -= k) {
        for(let t = 0; t < k; t++){
            let nxt = curr.next;

            curr.next = pre;
            pre = curr;
            curr = nxt;
        }
        const tmp = p0.next;
        p0.next.next = curr;
        p0.next = pre;
        p0 = tmp;
    }
    return dummy.next;
};

07 链表 - 快慢指针 ​

源文件：07-链表 - 快慢指针.md

来源：基础算法精讲 by 灵茶山艾府

视频精讲：链表 - 快慢指针

题目代码备注
876. 链表的中间结点代码
141. 环形链表代码
142. 环形链表 II代码
143. 重排链表代码
234. 回文链表代码*课后作业

例题 ​

876.链表中间节点 ​

  • 快慢指针，找中间值，脑海里模拟一下就行
js
var middleNode = function(head) {
    let fast = head,slow = head;
    while(fast !== null && fast.next !== null){

        fast = fast.next.next;
        slow = slow.next
    }
    return slow;
};

141.环形链表 ​

js
var hasCycle = function (head) {
    //快慢指针，模拟发现，必然会在环内相遇，判断相遇就行
    let fast = head, slow = head;

    while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        if(fast === slow) return true
    }
    return false;
};

142.环形链表二 ​

  • 在上一题的基础上，要找入口
  • 脑海里模拟

143.重排链表 ​

作业 ​

08 链表 - 删除系列 ​

源文件：08-链表 - 删除系列.md

来源：基础算法精讲 by 灵茶山艾府

视频精讲：链表 - 删除系列

题目代码备注
237. 删除链表中的节点代码脑筋急转弯
19. 删除链表的倒数第 N 个结点代码前后指针
83. 删除排序链表中的重复元素代码
82. 删除排序链表中的重复元素 II代码
203. 移除链表元素代码*课后作业
3217. 从链表中移除在数组中存在的节点代码*课后作业
2487. 从链表中移除节点代码*课后作业

例题 ​

237. 删除链表中的节点 ​

  • 值覆盖，next覆盖即可

19. 删除链表的倒数第 N 个结点 ​

  • 注意，需要引入dummy节点的情况通常是会对头节点有相关操作，可能是倒数第length个，所以要引入dummy
  • 法一，m+n===length，计算出m再移动即可
  • 法二，双指针，r移动n步，然后l，r一起移动直到 r.next ===null;
  • 不要忘记new操作符
js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    const dummy = new ListNode(0, head);
    let l = dummy, r = dummy;

    while (r && n--) r = r.next;
    // console.log('beforeBL', r)
    while (r && (r.next !== null)) {
        r = r.next;
        l = l.next;
    }
    if (l) {
        l.next = l.next.next;
    }
    // console.log('aftBL', l, r, dummy)
    return dummy.next;
};

83. 删除排序链表中的重复元素 ​

  • 一些细节问题，val，迭代逻辑
js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    let curr = head;

    while (curr && (curr.next !== null)) {
        //不要下意识使用value，造成奇奇怪怪的错误，这里用val
        if (curr.val === curr.next.val) {
            curr.next = curr.next.next;
        } else
            curr = curr.next;
    }
    // console.log('curr',curr,'head',head);
    return head;
};

82. 删除排序链表中的重复元素 II ​

  • 多画图模拟，画图模拟；
js
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    const dummy = new ListNode(0, head)
    let curr = head, pre = dummy;
    //重新梳理逻辑：当遇到重复值，要找出所有重复值，找完之后pre再进行移动
    while (curr && curr.next) {
        if (curr.val === curr.next.val) {
            //找到重复值的最后一个
            while (curr && curr.next && (curr.val === curr.next.val)) {
                curr = curr.next
            }
            pre.next = curr.next;
            //防止有连续的重复值
            curr = curr.next

        } else {
            //清除逻辑，跳过连续或者不连续的
            pre = curr;
            curr = curr.next;
        }
        // console.log(pre.val, curr.val, dummy)

    }
    return dummy.next;

作业 ​