思想

今天进入到哈希专题。所谓哈希，重点在于提高信息访问的速度。比如，原先查找一个数组中是否存在某个元素，要用 $O(n)$ 的遍历，如果用哈希表，或者说人话就是集合，那复杂度降为 $O(1)$。那么哈希就类似于防患于未然。

题目

1. Two Sum

两数之和，给了一个数组和一个目标，求数组中两个数的下标，s.t. 两数之和等于目标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;  // val -> idx

        for (int i = 0; i < nums.size(); i++) {
            if (mp.count(target - nums[i])) {
                return {i, mp[target- nums[i]]};
            }

            mp[nums[i]] = i;
        }

        return {};
    }
};

从第 1 题入手，看看哈希是怎么一回事。

如果没学过算法，直接暴力求解，是一个 $O(n^2)$ 的复杂度——一个二重循环，对每个位置的数，都考虑其他位置的数与之加和是否能得到目标。

如果考虑优化一下复杂度呢？

$O(n)$ 的遍历躲不开，但，能否把查找另外一个加数是否存在的过程优化成 $O(1)$？是的，可以。采用一个字典，记录值到下标的映射（为什么不是下标到值？没意义！nums 干什么吃的！）。每次遍历时，查查 counterpart 是否存在，若有，返回结果。

因为两数之和是两个数的事情，所以很可能找到第一个正确加数时，第二个加数还没读取到，导致循环无法结束。不必担心，待读取到第二个加数时会反过来定位到第一个加数，所以 OK。

49. Group Anagrams

把变位词分组。相同的变位词归到一组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;

        for (string str : strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].push_back(str);
        }

        vector<vector<string>> ans;

        for (auto& [k, v] : mp) {
            ans.push_back(v);
        }

        return ans;
    }
};

这题就是个简单的 GROUP BY，我觉得更重要的地方是理解一些 STL 方法。对每个字符串，排序后得到 key，随后附加到向量中。最后一个类似于 Python 解包的语法，把值转换为 vector。

128. Longest Consecutive Sequence

最长连续序列。给了一串数组，问，其中最长连续的数组有多长。比如，[1, 3, 2, 4, 100 ,5] 的结果是 5。

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:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());

        int ans = 0;

        for (int num : st) {
            if (st.count(num - 1) == 0) {  // valid start
                int length = 0;
                int curr = num;

                while (st.count(curr)) {
                    length++;
                    curr++;
                }

                ans = max(ans, length);
            }
        }

        return ans;
    }
};

这题要求我们用 $O(n)$ 的复杂度。所以即使排序后的处理更简单，那是 $O(n\log{n})$ 了，不符合要求。

不妨还是从排序的思路出发。排序的好处是，连续、中断，以及更新最大值的时机更容易判断。如果不排序，退而求其次，至少能定位到起点吧？那稍微友好一些，可以把所有元素放到集合中，如果元素的前驱不存在，说明是合法的起点。

上面的算法就是这个处理思路。当然，需要注意两点：

  • 在遍历时，需要注意是对 st 遍历，不要手滑，对向量遍历会 TLE，因为没去重；
  • 在对某个合法起点向后遍历时，需要用单独一个变量记录当前值，否则语义可能有问题（当然，我不确定这种迭代的方式改了会怎样）。

560. Subarray Sum Equals K

这题让我们找出子数组（必须连续），子数组的元素之和是 k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;  // sum -> cnt

        mp[0] = 1;

        int sum = 0;
        int ans = 0;

        for (int num : nums) {
            sum += num;

            if (mp.count(sum - k)) {
                ans += mp[sum - k];
            }

            mp[sum]++;
        }

        return ans;
    }
};

这题是一道前缀和的题目啊。之前在二叉树的专题里讲过一两道和前缀和有关的题目。

需要深入讲讲这里字典的含义。字典记录的是前缀和 -> 取得前缀和的次数。那么，在字典的构建过程中，假如处理到了下标 i，字典的含义是到 i 之前，取得的前缀和与其次数的映射。而 sum 的含义便是到 i 的前缀和。

理解了字典的含义，那 mp[0] = 1 的含义就不必多说了。

前缀和的利用方法是，两个前缀和相减得到的值的含义是一串连续的序列，这串序列的元素之和是这个值。这和题目的要求是一一对应的，我们要求的不就是连续序列使得元素的和是 k？

所以遍历 nums 的每个 num，每到达一个新的位置，得到 sum，表示以这个位置结尾得到的和。减去 k 得到了加和为 sum - k 的序列个数，这些序列都是从起点开始的，它的数量就是我们要的值。含义是以 num 所在位置结尾的连续序列个数，且加和为 k。

画个图。如果到当前位置为止，得到的 sum - k 的个数是 3，对应 3 个黑色的部分，那么白色部分就是要得到的连续数组。

1
2
3
■■■■□□□□□□□□□□□□▣
■■■■■■■□□□□□□□□□▣
■■■■■■■■■■■■□□□□▣