和为 K 的子数组——前缀和+哈希

**和为 K 的子数组**

在算法竞赛中，和为 K 的子数组问题是非常常见的题目。这个问题要求我们找出给定一个整数数组中的所有子数组，其元素之和等于 K。

本文将介绍一种高效的解决方案：使用前缀和和哈希表。这种方法可以在 O(n) 时间复杂度内找到所有和为 K 的子数组。

**前缀和**

首先，我们需要计算给定数组的前缀和。前缀和是指从数组第一个元素开始到当前元素之间的所有元素之和。

例如，如果我们有一个数组 `[1,2,3,4,5]`，那么其前缀和为：

* `prefix[0] =1`
* `prefix[1] =1 +2 =3`
* `prefix[2] =1 +2 +3 =6`
* `prefix[3] =1 +2 +3 +4 =10`
* `prefix[4] =1 +2 +3 +4 +5 =15`

前缀和可以使用以下公式计算：

`prefix[i] = prefix[i-1] + arr[i]`

其中 `arr[i]` 是当前元素。

**哈希表**

接下来，我们需要使用哈希表来存储前缀和的值。我们将使用一个哈希表 `hash` 来存储前缀和的值。

例如，如果我们有一个数组 `[1,2,3,4,5]`，那么其前缀和为：

* `prefix[0] =1`
* `prefix[1] =3`
* `prefix[2] =6`
* `prefix[3] =10`
* `prefix[4] =15`

我们将这些值存储在哈希表中：

`hash[prefix[0]] = {0}`
`hash[prefix[1]] = {0,1}`
`hash[prefix[2]] = {0,1,2}`
`hash[prefix[3]] = {0,1,2,3}`
`hash[prefix[4]] = {0,1,2,3,4}`哈希表 `hash` 中的值表示前缀和的索引。

**找到和为 K 的子数组**

现在，我们可以使用哈希表来找到和为 K 的子数组。

我们将遍历数组，并计算每个元素的前缀和。然后，我们将检查哈希表中是否存在一个前缀和值等于 `K - arr[i]`。

如果存在这样的值，我们将返回该值所对应的索引作为和为 K 的子数组。

例如，如果我们有一个数组 `[1,2,3,4,5]`，那么其前缀和为：

* `prefix[0] =1`
* `prefix[1] =3`
* `prefix[2] =6`
* `prefix[3] =10`
* `prefix[4] =15`

我们将计算每个元素的前缀和，并检查哈希表中是否存在一个前缀和值等于 `K - arr[i]`。

例如，如果 `K =7`，那么我们将检查：

* `hash[prefix[0]] = {0}`：不存在一个前缀和值等于 `7 -1 =6`
* `hash[prefix[1]] = {0,1}`：存在一个前缀和值等于 `3 -2 =1`，但它不是和为 K 的子数组* `hash[prefix[2]] = {0,1,2}`：不存在一个前缀和值等于 `7 -6 =1`
* `hash[prefix[3]] = {0,1,2,3}`：存在一个前缀和值等于 `10 -4 =6`，但它不是和为 K 的子数组* `hash[prefix[4]] = {0,1,2,3,4}`：不存在一个前缀和值等于 `7 -15 = -8`

因此，我们将返回空列表作为和为 K 的子数组。

**代码示例**

以下是使用前缀和和哈希表的 C++代码：

cpp#include <iostream>
#include <vector>
#include <unordered_map>

int main() {
 std::vector<int> arr = {1,2,3,4,5};
 int K =7;

 // 计算前缀和 std::vector<int> prefix(arr.size());
 for (int i =0; i < arr.size(); ++i) {
 if (i ==0) {
 prefix[i] = arr[i];
 } else {
 prefix[i] = prefix[i-1] + arr[i];
 }
 }

 // 使用哈希表找到和为 K 的子数组 std::unordered_map<int, std::vector<int>> hash;
 for (int i =0; i < arr.size(); ++i) {
 if (hash.find(prefix[i]) == hash.end()) {
 hash[prefix[i]] = {i};
 } else {
 hash[prefix[i]].push_back(i);
 }
 }

 std::vector<int> result;
 for (int i =0; i < arr.size(); ++i) {
 int target = K - arr[i];
 if (hash.find(target) != hash.end()) {
 for (int j : hash[target]) {
 if (j > i) {
 result.push_back(i);
 break;
 }
 }
 }
 }

 // 输出结果 std::cout << "和为 K 的子数组：";
 for (int i : result) {
 std::cout << arr[i] << " ";
 }
 std::cout << std::endl;

 return0;
}