算法 : 枚举 - Eureka的博客

591 字

3 分钟

算法 : 枚举

2026-04-06

算法

§0.1 枚举右，维护左#

对于 双变量问题，例如两数之和 $a_i + a_j = t$ ，可以枚举右边的 $a_j$ ，转换成 单变量问题，也就是在 $a_j$ 左边查找是否有 $a_i = t - a_j$ ，这可以用哈希表维护。

我把这个技巧叫做 枚举右，维护左。讲解: 1. 两数之和 - 力扣（LeetCode）

1
class Solution {
2
public:
3
    vector<int> twoSum(vector<int>& nums, int target) {
4
        unordered_map<int, int> idx; // 创建一个空哈希表
5
        for (int j = 0; ; j++) { // 枚举 j
6
            // 在左边找 nums[i]，满足 nums[i]+nums[j]=target
7
            auto it = idx.find(target - nums[j]);
8
            if (it != idx.end()) { // 找到了
9
                return {it->second, j}; // 返回两个数的下标
10
            }
11
            idx[nums[j]] = j; // 保存 nums[j] 和 j
12
        }
13
    }
14
};

§0.2 枚举中间#

对于有三个或者四个变量的问题，枚举中间的变量往往更好算。为什么？比如问题有三个下标，需要满足 $0 \le i < j < k < n$ ，对比一下：

枚举 $i$ ，后续计算中还需保证 $j < k$ 。
枚举 $j$ ，那么 $i$ 和 $k$ 自动被 $j$ 隔开，互相独立，后续计算中无需关心 $i$ 和 $k$ 的位置关系。所以枚举中间的变量更简单。

1
class Solution {
2
public:
3
    int minimumSum(vector<int>& nums) {
4
        int n = nums.size();
5
        vector<int> right(n);
6
        right[n - 1] = nums[n - 1];
7
        for(int i = n - 2; i > 1; i--){
8
            right[i] = min(nums[i], right[i + 1]);
9
        }
10

11
        int ans = INT_MAX;
12
        int pre = nums[0];
13
        for(int j = 1; j < n - 1; j++){
14
            if(pre < nums[j] && nums[j] > right[j + 1]){
15
                ans = min(ans, pre + nums[j] + right[j + 1]);
16
            }
17
            pre = min(pre, nums[j]);
18
        }
19
        return ans == INT_MAX ? -1 : ans;
20
    }
21
};