前缀和+哈希表_前缀和哈希

1 基础知识

1.1 哈希表：

哈希表是基本的数据结构。哈希表存储的是由键（Key）和值（value）组成的数据。例如，我们将每个人的性别作为数据进行存储，键为人名，值为对应的性别。

在哈希表中可以通过 键 来访问相应的 值。在上表中，通过人名可以获取相应的性别。在应用中，通常使用哈希表来计数或者记录某个元素的位置。

1.2 前缀和

对于数组 $nums$，定义它的前缀和 $s[0]=0$，$s[i+i]={\sum }_{j=0}^{i}nums\left[j\right]$ 。

例如 $nums=[1,2,-1,2]$ 的前缀和数组为 $s=[0,1,3,2,4]$。

通过前缀和，可以把 子数组的元素和转化为两个前缀和之差，即
$$\sum _{j=left}^{right}nums\left[j\right]=\sum _{j=0}^{right}nums\left[j\right]-\sum _{j=0}^{left-1}nums\left[j\right]=s\left[right+1\right]-s\left[left\right]$$

注1：为了方便计算，常用左闭右开区间 $[left,right)$ 来表示从 $nums[left]$ 到 $nums[right-1]$ 的子数组，此时子数组的和为 $s[righ]-s[left]$，子数组的长度为 $right-left$。

注2：为什么要定义 $s[0]=0$ 这样一个表示空数组的元素和呢？如果需要计算的刚刚好是一个前缀和，比如说是前 2 个元素的和，这时通过计算 $s[2]-s[0]$ 即可得到。通过定义 $s[0]=0$ 任意子数组都可以用两个前缀和之差表示。

1.3 同余定理

同余定理是数论中的一个重要概念，给定一个正整数 $m$，如果两个整数 $a、b$ 满足 $a-b$ 能够被 $m$ 整除即 $(a-b)/m$ 得到的是一个整数，那么称整数 $a$ 与 $b$ 对模 $m$ 同余，记作 $a\equiv b(modm)$。

若 $a、b$ 均为非负数，则有 $amodm=bmodm$；

若 $a<0、b>=0$，则有 $amodm+m=bmodm$；

因此，为了省去判断 $a$ 正负的麻烦，上述等式左侧可写成 $(amodm+m)modm$，于是有 $(amodm+m)modm=bmodm$。

2 哈希表的应用

有些题目虽然是简单题，但是能够考察许多基础的知识点。比如两数之和这道题，在有序数组中找出和为 $target$ 的两个元素并返回下标。对于这道经典的题目，有许多种解法，暴力枚举、双指针和哈希表的方法等。这里主要对使用哈希表的方法进行讲解。

2.1 思路讲解

我们需要返回的和为目标值的两个元素的下标，可以维护一个键值对为元素与位置下标的哈希表 $mp$。因为需要找到两个元素 $nums[i]$ 和 $nums[j]$ 使得 $nums[i]+nums[j]=target$，移项可得：$nums[i]=target-nums[j]$ 于是在遍历数组的时候记遍历的当前元素为 $nums[i]$，如果在哈希表中能够找到 $target-nms[i]$，返回的 { i , m p [ t a r g e t − n m s [ i ] ] } \{i,mp[target-nms[i]]\} {i,mp[target−nms[i]]} 即是最终的答案。

通常我们只进行一次遍历，在寻找 $target-nms[i]$ 的同时更新哈希表。

2.2 代码实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            if (mp.find(target - nums[i]) != mp.end()) {
                return {i, mp[target - nums[i]]};
            }
            mp[nums[i]] = i;
        }

        return {-1, -1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.3 复杂度

时间复杂度：$O(n)$，$n$ 为数组的长度。
空间复杂度：$O(n)$，因为需要维护一个哈希表。

3 前缀和与哈希表

前面已经介绍了哈希表和前缀和的基础知识，但在我们来看一下它们是如何搭配使用的。

3.1 面试题 17.05. 字母与数字

3.1.1 题目要求

题目来源：LeetCode 面试题 17.05. 字母与数字
给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

和本题类似的还有 LeetCode 525. 连续数组。

3.1.2 思路讲解

子数组内包含的字母和数字的个数相同，若用1表示数字，-1表示字母，则符合上述要求的子数组元素之和为0。利用前缀和来求子数组的和，那么有$s[r]-s[l]==0$，题目就等价于在修改后的数组中找到相同的前缀和并使得 $r-l$ 最大。

题目要求，在数组 $array$ 中寻找一个最长子数组，使得子数组内字母和数字的个数相等。现在，如果 $array[i][0]$ 是字母，则将其视为 1；否则视为 -1。经过上述转化之后，原问题等价于 【找到一个最长子数组，使数组元素之和为0】。对于子数组的元素之和，我们可以利用前缀和来计算。子数组元素之和为0，那么表示子数组元素之和的两个前缀和之差为0，进而有这两个前缀和相等。

遍历前缀和 $s$ 的同时，用哈希表 $first$ 记录 $s[i]$ 第一次出现的位置，我们需要计算的就是 $i-first[s[i]]$ 的最大值，记录下取得最大值时子数组的始末位置，最后输出最长的子数组。

3.1.3 代码实现

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int n = array.size(), s[n+1];
        s[0] = 0;

        for (int i = 0; i < n; ++i) {
            s[i+1] = s[i] + (isalpha(array[i][0]) ? 1 : -1);
            
        }

        unordered_map<int, int> last;
        int start = 0, end = 0;     // 符合要求的数组 [start, end)
        for (int i = 0; i <= n; ++i) {
            auto it = last.find(s[i]);
            if (it == last.end()) {
                last[s[i]] = i;
            }
            else {
                if (i - it->second > end - start) {
                    start = it->second;
                    end = i;
                }
            }
        }

        return {array.begin() + start, array.begin() + end};
    }
};
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

3.1.4 复杂度

时间复杂度：$O(n)$，$n$ 为数组 $array$ 的长度。
空间复杂度：$O(n)$。

3.2 子数组和的问题

在子数组和的问题中都是利用前缀和的知识来解决子数组和的问题，并利用哈希表来降低时间复杂度，接下来的题解都是针对如何利用哈希表来描述的。只给出了思路分析，没有具体的代码，具体代码可以参考原题官方代码。

3.2.1 连续的子数组和

题目来源：523. 连续的子数组和
题目要求判断判断数组 $nums$ 中是否有和为 $k$ 的倍数，且子数组长度不小于 2 的子数组。子数组的和可以利用前缀和求出，用左闭右开区间 $[l,r)$ 来表示从 $nums[l]$ 到 $nums[r-1]$ 的子数组，此时子数组的和为 $s[r]-s[l]$，子数组的长度为 $r-l$。

如果 $s[r]-s[l]$ 为 $k$ 的倍数，则有 $s[r]$ 和 $s[l]$ 同余，即 $s[r]modk=s[l]modk$。于是可以用维护一个哈希表 $mp$ 用来记录前缀和模上 $k$ 的值上一次出现的位置：

• 如果该值存在于哈希表中，则取出上次出现的位置 $preIdx$，计算得到此时子数组的长度 $i-preIdx$，该子数组的元素和是 $k$ 的整数倍；如果 $i-preIdx>=2$，则存在符合条件的连续子数组返回 $true$，如果遍历完前缀和依然不满足整数倍和长度的要求则返回 $false$。
• 如果该值不存在于哈希表中，则将该值与当前下标的键值对存入哈希表。

3.2.2 和为 K 的子数组

题目来源：560. 和为 K 的子数组
利用前缀和得到子数组的和为 $s[r]-s[l]$ 表示的是数组 $nums[l]$ 到 $nums[r-1]$ 的子数组的和，要求和为 $k$ 则有 $s[r]-s[l]=k$，移项有 $s[r]-k=s[l]$，于是题目转化为统计数组中有多少前缀和为 $s[r]-k$ 的 $s[l]$ 。

维护一个哈希表，以前缀和 $s$ 和对应出现的次数作为键值对，如何遍历的到前缀和 $s$ 时，哈希表中存在 $s-k$ ，则加入答案中。并且要更新哈希表。

3.2.3 和可被 K 整除的子数组

题目来源：974. 和可被 K 整除的子数组
根据前缀和的知识，常用左闭右开区间 $[l,r)$ 来表示从 $nums[l]$ 到 $nums[r-1]$ 的子数组，此时子数组的和为 $s[r]-s[l]$。题目要求子数组的子数组的和可以被 k 整除，则有 $(s[r]-s[l])modk==0$，根据同余定理有，$s[r]modk=s[l]modk$ 。

维护一个以前缀和模 $k$ 的值为键，出现次数为值的哈希表 $cnts$ ，遍历前缀和 $s$ 的同时，更新哈希表。最后的答案就是 $smodk$ 的个数，即 $cnts[smodk]$。

还需要注意一个边界条件，$cnts[0]=1$，即前缀和本身可以被 $k$ 整除的情况。

不同语言的负数取模的值不一定相同，有的语言负数取模的结果为负数，这个时候需要特殊处理，比如在 C++ 中，以 $(smodk+k)modk$ 的方式进行处理，而在 Python 语言中就不需要特殊处理。

3.2.4 统计美丽子数组数目

题目来源：2588. 统计美丽子数组数目
根据题目分析可以知道美丽子数组内元素的二进制数任意比特位上的 1 出现的次数都是偶数，于是异或后的值为 0。$s[i]、s[j]$ 分别表示数组前 $i$ 个和前 $j$ 个元素的前缀异或和（$j<i$），$s[i]\wedge s[j]$ 表示 $nums[j]$ 到 $nums[i]$ 子数组元素的异或值， 根据美丽子数组元素异或后为 $0$ 的特点有 $s[i]\wedge s[l]=0$，因此有 $s[i]=s[j]$。于是统计美丽子数组的个数等价于统计 $nums$ 数组内相同的 前缀异或和 的个数。

遍历所有的前缀异或和，取出哈希表中当前异或前缀和的个数加入到答案中，并更新哈希表。

4 总结

题目中出现 子数组 的字样，就要联想到前缀和的知识，这个前缀不单单是和也可以是异或和、差、积，还有可能是后缀和等等。

哈希表的取数据时间复杂度是 $O(1)$，有的时候可以利用哈希表来降低时间复杂度，主要考察如何设计哈希表的使用。

有的题目中还会考察一些数学知识，比如前面讲到的数论中同余定理，只能说遇到了就积累一下，学有余力的话可以找找相关书籍研究以下。