算法 : 枚举 - Eureka的博客

872 字

4 分钟

算法 : 枚举

2026-04-25

2026-05-03

常用数据结构

算法

/

常用数据结构

§枚举右，维护左#

对于 双变量问题，例如两数之和 $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 \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
};

§遍历对角线#

1
class Solution {
2
public:
3
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
4
        int m = grid.size(), n = grid[0].size();
5
        for(int k = 0; k < m + n; k++){
6
            int min_j = max(n - k, 0);
7
            int max_j = min(m + n - 1 - k, n - 1);
8
            vector<int> a;
9
            for(int j = min_j; j <= max_j; j++){
10
                a.push_back(grid[k + j - n][j]);
11
            }
12
            if(min_j > 0){
13
                ranges::sort(a);
14
            }else{
15
                ranges::sort(a,greater());
16
            }
17
            for(int j = min_j; j <= max_j; j++){
18
                grid[k + j - n][j] = a[j - min_j];
19
            }
20
        }
21
        return grid;
22
    }
23
};