[算法/数据结构]系列 华为面试原题：和为n的子串（前缀和+哈希表）

[算法/数据结构]系列 华为面试原题：和为n的子串（前缀和+哈希表）

文章目录

• [算法/数据结构]系列 华为面试原题：和为n的子串（前缀和+哈希表）
• 面试原题
• 样例分析
• 代码及思路

面试原题

输入一串只有0和1的数组，返回输入和为n的子串的个数。

样例：
输入：[0 1 1 1 0 0], n = 3
输出：6

样例分析

输入数组：[0, 1, 1, 1, 0, 0]
目标和：n = 3
我们需要找到所有和为 3 的连续子数组（子串）。从给出的结果来看，允许 0 被并入子串。

前缀和：广泛用于解决区间查询问题，尤其是对数组元素进行快速求和（有些题目可能转换为异或）。它通过保存计算数组前n个数的结果，避免了重复计算，从而显著提高查询效率。一般会配合哈希表一起使用以获得最优的效率。

所有和为 3 的子串如下：
[0, 1, 1, 1]（索引范围 [0, 3]）
[1, 1, 1]（索引范围 [1, 3]）
[1, 1, 1, 0]（索引范围 [1, 4]）
[1, 1, 1, 0, 0]（索引范围 [1, 5]）
[0, 1, 1, 1, 0]（索引范围 [0, 4]）
[0, 1, 1, 1, 0, 0]（索引范围 [0, 5]）
这样就总共有 6 个子串满足条件。

代码及思路

前缀和一般表示为：
s u m [ n ] = s u m [ n − 1 ] + n u m s [ n ] sum[n] = sum[n - 1] + nums[n] sum[n]=sum[n−1]+nums[n]
如果问题可以由如上递推关系表示，且可以使用内存换时间，那么可以使用前缀和。

公式中的 + + +也可以替换为 ⊕ \oplus ⊕等其他任何可能的操作符。

实现的代码如下：
使用时候需要特别注意 对储存前缀和出现次数的哈希表的初始化

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    vector<int> nums = {0, 1, 1, 1, 0, 0}; // 输入数组
    int n = 3; // 目标和

    unordered_map<int, int> prefixSumCount; // 哈希表存储前缀和出现的次数  <前缀和,次数>
    prefixSumCount[0] = 1; // 初始化：前缀和为0的次数为1
    int sum = 0;           // 当前前缀和
    int count = 0;         // 符合条件的子数组个数

    for (int num : nums) {
        sum += num; // 更新前缀和

        // 查找是否存在前缀和为 sum - n 的记录
        if (prefixSumCount.find(sum - n) != prefixSumCount.end()) {
            count += prefixSumCount[sum - n]; // 增加符合条件的子数组个数
        }

        // 更新当前前缀和在哈希表中的出现次数
        prefixSumCount[sum]++;
    }

    cout << "result is:" << count << endl;

    return 0;
}

学习资料链接