枚举算法即遍历已有的集合，判断哪些元素符合要求，最终求解问题。

例如 LeetCode 第一题，两数之和：

1
2
3
4
5
6
7

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

示例 1：

  输入：nums = [2,7,11,15], target = 9
  输出：[0,1]
  解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

暴力枚举

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return { 0, 0 };
    }
};

时间复杂度：\(O(N^2)\) ，空间复杂度：\(O(1)\)

保留额外信息优化

枚举算法优化技巧：枚举前面的元素时保存已知信息，枚举到后面时利用前面信息直接求解

本题求解 a + b = target 可以转换为 b = target - a ，遍历 a 时在表中查找前面是否出现过对应的 b ，如果出现直接返回，否则将 a 加入表中，供后面的遍历查询

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> cache;
        for (int i = 0; i < nums.size(); i++) {
            int a = nums[i];
            int b = target - a;
            auto iter = cache.find(b);
            if (iter != cache.end()) {
                return {iter->second, i};
            } else {
                cache[a] = i;
            }
        }
        return { 0, 0 };
    }
};

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

类似例子：

1
2
3
4
5
6

设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。

示例 2：

输入：nums = [5,6,5,6], target = 11
输出：[[5,6],[5,6]]

同样 a + b = target ，但是存在多对，因此表格中要保存 b 出现的次数，当匹配一次时，次数减 1 ，减到 0 时从表中移除

 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:
    vector<vector<int>> pairSums(vector<int>& nums, int target) {
        unordered_map<int, int> cache;
        vector<vector<int>> ans;

        for (auto num : nums) {
            int diff = target - num;
            auto iter = cache.find(diff);
            if (iter == cache.end()) {
                cache[num]++;
            } else {
                ans.emplace_back(vector<int>{iter->first, num});
                iter->second--;
                if (iter->second <= 0) {
                    cache.erase(iter);
                }
            }
        }
        return ans;
    }
};