Coding技巧

ZaynPei Lv6
  2025-10-09 22:00 2025-10-09 22:00 Created   2025-11-20 19:28:39 2025-11-20 19:28:39 Updated      4.6k Words  17 Mins

二分查找

二分查找 (Binary Search) 是一种高效的查找算法，适用于在有序数组或列表中查找特定元素。它通过不断将搜索范围减半来快速定位目标元素，从而大大减少了查找的时间复杂度。

代码实现如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int binarySearch(const vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防止溢出

        if (nums[mid] == target) {
            return mid;  // 找到目标元素，返回其索引
        } else if (nums[mid] < target) {
            left = mid + 1;  // 目标在右半部分
        } else {
            right = mid - 1;  // 目标在左半部分
        }
    }

    return -1;  // 未找到目标元素
    // return left;  // 如果需要返回插入位置, 可以返回 left
}
> 最后的 left 指向第一个大于等于 target 的位置, 也就是插入位置.

需要注意的关键点是:

  • 使用闭区间搜索, 即 left 和 right 都是包含在搜索范围内的. 此时循环条件必须是 left <= right. 因为当 left == right 时, 仍然需要检查这个位置的元素是否等于 target.
  • 同时, 此时所有情况的边界修改都必须是 left = mid + 1 或 right = mid - 1, 不能是 left = mid 或 right = mid, 否则会导致死循环.

例如, 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if(n==0) return {-1,-1};
        
        // left-bound
        int left = 0, right = n-1;
        int leftBound = -1;
        while(left<=right){
            int mid = left + (right-left)/2;
            if(nums[mid]>=target){
                if(nums[mid]==target) leftBound = mid;  // 记录左边界, 因为有可能是这个位置, 也可能不是, 继续往左找
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        if(leftBound==-1) return {-1,-1};

        // right-bound
        left = 0, right = n-1;
        int rightBound = -1;
        while(left<=right){
            int mid = left + (right-left)/2;
            if(nums[mid]<=target){
                if(nums[mid]==target) rightBound = mid;
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return {leftBound, rightBound};
    }
};

滑动窗口

滑动窗口是一种用于处理数组或字符串中连续子序列问题的高效算法技巧。它通过维护一个动态调整的窗口来遍历数据结构，从而避免了重复计算，提高了算法的效率。

固定长度与可变长度滑动窗口

按照窗口的长度是否固定，滑动窗口可以分为两种类型：

  1. 固定长度滑动窗口 (Fixed-size Sliding Window)：窗口的大小在整个过程中保持不变。适用于寻找满足某种条件的固定长度子序列的问题。例如，寻找数组中所有长度为k的子数组的最大和。
  2. 可变长度滑动窗口 (Variable-size Sliding Window)：窗口的大小可以根据需要动态调整。适用于寻找满足某种条件的任意长度子序列的问题。例如，寻找字符串中包含所有目标字符的最短子串。

固定长度滑动窗口

固定长度滑动窗口的基本思想是维护一个固定大小的窗口，并通过移动窗口来遍历数组或字符串。 - 初始化时，窗口覆盖数据结构的前k个元素，计算初始窗口的相关信息（如和、最大值等）。 - 循环遍历, 逐步向右移动窗口，每次移动一位，通过加入新元素并移除旧元素来更新窗口的信息。

例如, 寻找数组中所有长度为k的子数组的最大和: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int maxSumSubarray(const vector<int>& nums, int k) {
    int n = nums.size();
    if (n < k) return -1;  // 不合法的输入

    int maxSum = 0;  // 记录最大和
    int cur = 0;  // 记录当前窗口和

    // 初始化窗口
    for (int i = 0; i < k; i++) {
        cur += nums[i];
    }
    maxSum = cur;

    // 循环移动窗口, 总共n元素, 已经处理了k个, 还剩n-k个元素待处理, 因此i从[1开始到n-k]
    for (int i = 1; i <= n-k; i++) {
        cur += nums[k-1+i] - nums[i-1];  // 更新窗口和
        maxSum = max(maxSum, cur);
    }
    return maxSum;
}
对于其他问题, 只要窗口大小固定, 都可以使用类似的方法进行处理, 基本套路都是两步走: 初始化窗口 -> 移动窗口并更新结果.

示例

有这样一道题(leetcode239): 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

看起来是固定长度滑动窗口问题, 但是如果直接用上面的固定长度滑动窗口方法, 每次移动窗口都需要遍历窗口内的 k 个元素来找最大值, 时间复杂度是 O(n*k), 会超时.

为什么呢? 因为上面的其他固定长度滑动窗口问题, 每次移动窗口时, 只需要加上新元素, 减去旧元素, 窗口内的信息更新是 O(1) 的, 但是求最大值就不行了, 每次移动窗口时, 上一次的最大值可能被移出了窗口, 而我们又没有记录其他元素的信息, 只能遍历窗口内的 k 个元素来找最大值, 这样时间复杂度就是 O(n*k) 了.

为了解决这个问题, 我们需要使用一种特殊的数据结构——单调队列，来维护窗口内的元素顺序, 使得我们可以在 O(1) 时间内获取窗口的最大值. 具体代码可以参考队列部分的笔记.

可变长度滑动窗口

可变长度滑动窗口的核心思想是通过调整窗口的左右边界来满足特定条件。通常使用两个指针/索引（left 和 right）来表示窗口的边界。 - 初始化时，left 和 right 指针都指向数据结构的起始位置。 - 循环遍历, 通过移动 right 指针来扩展窗口，直到窗口满足某种条件（如包含所有目标字符）。 - 然后通过移动 left 指针来收缩窗口，直到窗口不再满足条件。在这个过程中，记录满足条件的窗口信息（如最短长度、最大长度等）。 - 重复上述过程，直到 right 指针遍历完整个数据结构。

注意: 可变长度滑动窗口通常需要一个辅助数据结构（如哈希表）来记录窗口内的元素信息，以便快速判断窗口是否满足条件。

一般可变长度滑动窗口的题型有三种: 1. 找出满足某种条件的最小子数组/子字符串。 2. 找出满足某种条件的最大子数组/子字符串。 3. 计算满足某种条件的子数组/子字符串的数量。

最小数组/子串/序列

例如, 给定一个含有 n 个正整数的数组和一个正整数 target , 找出该数组中满足其和 ≥ target 的长度最小的连续子数组的长度: (最小长度子数组问题) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();

    int left=0, right=0;
    int minlen = INT_MAX;
    int cur = 0;       // 因为是求和问题, 不需要哈希表, 只需要一个变量记录当前窗口和即可

    for(right=0;right<n;right++){  // 扩展窗口

        cur += nums[right];  // 增加当前窗口和

        while(cur>=target){  // 收缩窗口
            minlen = min(right-left+1, minlen);
            cur -= nums[left];  // 一定注意先减去left位置的元素, 再left++!!!!!
            left++;
        }
    }
    return minlen==INT_MAX? 0: minlen;
}
还有一道题, 给定一个字符串 s 和一个字符串 t ，找出 s 中涵盖 t 所有字符的最小子串。 (最小覆盖子串问题) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    string minWindow(string s, string t) {
        int m = s.size();
        int n = t.size();
        if(m<n||m==0||n==0) return string();

        // 记录目标字符串 t 中每个字符的频次, 从而将问题转化为判断当前窗口是否包含了 t 中所有字符及其频次
        unordered_map<char, int> target_counts;    // 覆盖子串问题, 需要记录的内容更多, 因此需要使用哈希表
        for(char c:t){
            target_counts[c]++;
        }

        int required = target_counts.size();    // 需要覆盖的不同字符的数量
        int formed = 0;   // 记录当前窗口中满足要求的不同字符的数量

        unordered_map<char, int> window_counts;  // 记录当前窗口中每个字符的频次

        // 记录string, 需要一个开头位置和长度
        int min_start = 0;
        int min_len = INT_MAX;

        int left = 0;
        for(int right=0;right<m;right++){
            char c = s[right];
            // 更新窗口内字符频次
            window_counts[c]++;
            if(target_counts.contains(c) && window_counts[c]==target_counts[c]){
                formed++;
            }

            // 条件满足, 尝试收缩窗口
            while(left<=right&&formed==required){
                int curr_len = right-left+1;
                if(curr_len<min_len){
                    min_len = curr_len;
                    min_start = left;
                }
                char c_left = s[left];
                if(target_counts.contains(c_left)&&window_counts[c]==target_counts[c]){
                    formed--;
                }
                window_counts[c_left]--;
                left++;
            }
        }
        // 如果没有找到符合条件的子串, 则返回空字符串
        return (min_len==INT_MAX)? "":s.substr(min_start, min_len);
    }
};
这道题同样使用了可变长度滑动窗口的思路, 通过维护一个窗口, 不断扩展和收缩窗口来找到最小覆盖子串. 不过这道题更加困难的点在于, 我们需要同时维护两个哈希表(上一题目只需要维护一个变量, 和目标和变量比较), 一个是目标字符串 t 中字符的频次, 另一个是当前窗口中字符的频次. 通过比较这两个哈希表来判断当前窗口是否满足条件.

理论上来说, 这道题记录窗口内信息只需要两个哈希表, 但是为了方便判断当前窗口是否满足条件, 我们还引入了两个变量: required 和 formed, 分别记录需要覆盖的不同字符的数量和当前窗口中满足要求的不同字符的数量. 这样可以避免每次都遍历哈希表来判断是否满足条件, 提高了效率.

最大数组/子串/序列

又例如, 给定一个字符串 s , 求至多包含两个不同字符的最长子字符串的长度: (最大长度子字符串问题, LC 159) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int lengthOfLongestSubstringTwoDistinct(string s) {
    int n = s.size();
    if (n < 3) return n;  // 特殊情况处理

    int left = 0, right = 0;
    int maxLen = 2;
    unordered_map<char, int> charCount;  // 记录窗口内字符的出现次数

    for (right = 0; right < n; right++) {  // 扩展窗口
        charCount[s[right]]++;

        while (charCount.size() > 2) {  // 收缩窗口, 直到左边界到达和右边界相同字符的位置

            charCount[s[left]]--;
            left++;
        }

        maxLen = max(maxLen, right - left + 1);  // 更新最大长度
    }
    return maxLen;
}
> 其实, 之所以可以滑动窗口解决, 一个必不可少的条件就是连续性, 也就是说问题本质上是求一个连续子数组或者连续子字符串的问题, 这样才能用滑动窗口来解决.

计算子数组/子串的数量

下一个示例则是求子数组个数的问题: 给你一个整数数组 nums 和一个 正整数 k , 请你统计有多少满足 「 nums 中的最大 元素」至少出现 k 次(越多越行)的子数组，并返回满足这一条件的子数组的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        long long n = nums.size();
        int left=0, right=0;
        long long sum=0;

        int max_num=0;      // 记录当前窗口内的最大值
        long long max_sum=0;    // 记录当前窗口内最大值的个数
        for(int i=0;i<n;i++){
            max_num = max(nums[i], max_num);  // 找到数组中的最大值
        }

        for(right=0;right<n;right++){
            if(nums[right]==max_num) max_sum++;  // 记录当前窗口内最大值的个数
            while(max_sum>=k){  // 收缩窗口, 不过是满足条件时
                sum+=n-right;   // 因为要求子数组个数, 所以每次符合条件进入收缩窗口时, 这个数组右边界到数组末尾的所有子数组都是符合条件的
                if(nums[left]==max_num) max_sum--;  // 先减去left位置的元素对最大值个数的影响
                left++;  // 再移动左指针
            }
        }
        return sum;
    }
};

还有一个经典问题: 给一个数组的分数定义为数组之和乘以数组的长度。比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。(越小越行)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        long long n = nums.size();
        long long sum = 0;
        long long left = 0, right = 0;
        long long cur_sum = 0;

        for(right=0;right<n;right++){
            cur_sum += nums[right];  // 增加当前窗口和
            while(cur_sum*(right-left+1)>=k){  // 收缩窗口, 如果不满足条件时
                cur_sum -= nums[left];  // 先减去left位置的元素对窗口和的影响
                left++;  // 再移动左指针
            }
            sum += (right-left+1);  // 增加符合条件的子数组个数, 这里因为求的是小于k的子数组个数, 所以所有以right结尾的子数组都是符合条件的
        }
        return sum;
    }
};

回顾上面两道题, 可以发现, 求子数组个数的问题, 每次满足条件时, 以right结尾的所有子数组, 或者是以left开头的所有子数组, 都是符合条件的, 这样就可以快速统计子数组个数. 也就是当窗口 [left, right] 满足某个条件时，其内部的某些子数组（或外部的某些超数组）也必然满足条件。我们利用这个性质来批量计数。

而且还可以发现, 第一题收缩窗口时是满足条件时收缩窗口, 第二题则是不满足条件时收缩窗口, 这取决于你要统计的子数组是“以 left 开头”还是“以 right 结尾”。

策略 策略一：满足时收缩 策略二：不满足时收缩
条件类型 “至少”型 (如 sum ≥ k) “至多”型 (如 sum <= k)
统计对象 所有以 left 为起点的达标数组 所有以 right 为终点的达标数组
while 循环条件 while (条件满足) while (条件不满足)
收缩 left 的目的 统计完 left 后，移动到下一个起点 修复窗口，使其重新满足条件
计数公式 total += n - right; (在 while 内部) total += right - left + 1; (在 for 循环内, while 外部)
恰好包含 k 个元素

除此之外, 还有一种是”恰好”型的问题, 例如求恰好包含 k 个不同字符的最长子字符串, 这种问题可以转化为”至多”型问题来解决, 即: 恰好包含 k 个不同字符的最长子字符串 = 包含 至多 k 个不同字符的最长子字符串 - 包含 至多 (k-1) 个不同字符的最长子字符串.

或者也可以转换为”至少”型问题来解决, 即: 恰好包含 k 个不同字符的最长子字符串 = 包含 至少 k 个不同字符的最长子字符串 - 包含 至少 (k+1) 个不同字符的最长子字符串.

例如给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的非空子数组。(二元指的是数组中元素只有0和1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int mostk(vector<int>& nums, int goal){
        int n = nums.size();
        int left=0, right=0;
        int sum=0;
        int level=0;

        for(right=0;right<n;right++){
            level+=nums[right];
            while(level>=goal&&left<=right){  // 符合条件时收缩
                sum+=n-right;
                level-=nums[left];
                left++;
            }
        }
        return sum;
    }
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        return mostk(nums, goal)-mostk(nums, goal+1);  // 转换为"至少"型问题, 包含 至少 k 个不同字符的最长子字符串 - 包含 至少 (k+1) 个不同字符的最长子字符串
    }
};

枚举技巧

侧重于解决问题的通用思维方式，特别是如何优化循环和遍历。

  • 枚举右，维护左：一种将 O(n2) 复杂度（双变量）问题优化到 O(n)（单变量）的常用技巧，通常与哈希表结合使用。
  • 枚举中间：处理三元组或四元组问题（如 i < j < k）的有效策略，通过固定中间变量 j，将问题分解为两个独立的子问题（处理 i 和 k）。
  • 遍历对角线：针对矩阵问题的特定遍历方式。

其余

递归

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

  • 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

  • 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

  • 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

另一种算法, 回溯, 其实是递归的副产品，只要有递归就会有回溯。

递归时如果超时, 可能是递归时对某些元素重复计算了, 这时可以考虑用记忆化搜索(Memoization)来优化递归算法, 即可以用一个哈希表来缓存已经计算过的结果, 避免重复计算.

在函数的开始先检查哈希表中是否已经存在该结果, 如果存在则直接返回该结果, 否则继续计算并将结果存入哈希表中.

例如LeetCode 337

On this page
Coding技巧
  1. 二分查找
  2. 滑动窗口
    1. 固定长度与可变长度滑动窗口
      1. 固定长度滑动窗口
        1. 示例
      2. 可变长度滑动窗口
        1. 最小数组/子串/序列
        2. 最大数组/子串/序列
        3. 计算子数组/子串的数量
        4. 恰好包含 k 个元素
  3. 枚举技巧
  4. 其余
    1. 递归