560. 和为K的子数组

# 题目

## 560. 和为 K 的子数组

[https://leetcode-cn.com/problems/subarray-sum-equals-k/](https://leetcode-cn.com/problems/subarray-sum-equals-k/)

给定一个整数数组和一个整数 **k，**你需要找到该数组中和为 **k** 的连续的子数组的个数。

**示例 1 :**

```
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
```

**说明 :**

1. 数组的长度为 [1, 20,000]。
2. 数组中元素的范围是 [-1000, 1000] ，且整数 **k** 的范围是 [-1e7, 1e7]。

# 题解

## 思路

两重循环遍历查询，但最后一个测试用例超时、

## 代码

```javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    const length = nums.length;
    let ans = 0;
    let sum;
    for(let i = 0; i < length; i++){
        sum = 0;
        for(let j = i; j < length; j++){
            sum += nums[j];
            if(sum === k){
                ans++;
            }
        }
    }
    return ans;
};
```

## 官方

### 1、暴力法（超时）

索引 i 和 j 确定一个子数组，枚举出所有子数组，子数组求和 == k 的话则 count++。
遍历 i、 遍历 j、 从 i 到 j 的累加求和。 三重循环，时间复杂度O(n^3)

```javascript
const subarraySum = (nums, k) => {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < nums.length; j++) {
      let sum = 0;
      for (let q = i; q <= j; q++) {
        sum += nums[q];
      }
      if (sum == k) count++;
    }
  }
  return count;
};
```

### 2、去除重复计算

- 求和时：上轮迭代求了 i 到 j - 1 的和，这轮就没必要从头求 i 到 j 的和。
- 去掉内层循环，用一个变量保存上次的求和结果，每次累加当前项即可。
- 依旧是穷举，时间复杂度：O(n^2)。还能再优化吗？
- Runtime: 900 ms, faster than 5.03% of Go online submissions

```javascript
const subarraySum = (nums, k) => {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      if (sum == k) count++;
    }
  }
  return count;
};
```

### 3、引入前缀和

- 前缀和：nums 的第 0 项到 当前项 的和。
- 用数组 prefixSum 表示，prefixSum[x]：第 0 项到 第 x 项 的和。
  
  ```
  prefixSum[x] = nums[0] + nums[1] +…+nums[x]
  ```
- nums 的某项 = 两个相邻前缀和的差：
  
  ```
  nums[x] = prefixSum[x] - prefixSum[x - 1]
  ```
- nums 的 第 i 到 j 项 的和，有：
  
  ```
  nums[i] +…+nums[j]=prefixSum[j] - prefixSum[i - 1]
  ```
- 当 i 为 0，此时 i-1 为 -1，我们故意让 prefixSum[-1] 为 0，使得通式在i=0时也成立：
  
  ```
  nums[0] +…+nums[j]=prefixSum[j]
  ```

#### 题目的等价转化

- 题意：有几种 i、j 的组合，使得从第 i 到 j 项的子数组和等于 k。
  ↓ ↓ ↓ 转化为 ↓ ↓ ↓
- 有几种 i、j 的组合，满足 prefixSum[j] - prefixSum[i - 1] == k。
- 可以通过求出 prefixSum 数组的每一项，再看哪些项相减等于k，求出count。
  但该通式有 2 个变量，需要两层循环才能找出来，依旧是 O(n^2)。

#### 不用求出 prefixSum 数组

- 其实我们不关心具体是哪两项的前缀和之差等于k，只关心等于 k 的前缀和之差出现的次数c，就知道了有c个子数组求和等于k。
- 遍历 nums 之前，我们让 -1 情况下的前缀和为 0，这样通式在边界情况也成立。即在遍历之前，map 初始放入 0:1 键值对。
- 遍历 nums 数组，求每一项的前缀和，统计对应的出现次数，键值对方式存入 map。
- 边存边查看 map，如果 map 中存在 key 为「当前前缀和 - k」，说明这个之前出现的前缀和，满足「当前前缀和 - 该前缀和 == k」，它出现的次数，累加给 count。

#### 复盘总结

- 每个元素对应一个“前缀和”
- 遍历数组，根据当前“前缀和”，在 map 中寻找「与之相减 == k」的历史前缀和
- 当前“前缀和”与历史前缀和，差分出一个子数组，该历史前缀和出现过 c 次，等价于当前项找到 c 个子数组求和等于 k。
- 遍历过程中，c 不断加给 count，最后返回 count
  
  时间复杂度 O(n) 。空间复杂度 O(n)

```javascript
const subarraySum = (nums, k) => {
  const map = { 0: 1 };
  let prefixSum = 0;
  let count = 0;

for (let i = 0; i < nums.length; i++) {
    prefixSum += nums[i];

if (map[prefixSum - k]) {
      count += map[prefixSum - k];
    }

if (map[prefixSum]) {
      map[prefixSum]++;
    } else {
      map[prefixSum] = 1;
    }
  }
  return count;
};
```