> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/niu-ke-0125-zhong-deng-he-weikde-lian-xu-zi-shu-zu.md).

# 和为K的连续子数组

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-29%2022%3A33%3A01\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E5%89%8D%E7%BC%80%E5%92%8C\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#前缀和) [![](https://img.shields.io/static/v1?label=\&message=%E5%93%88%E5%B8%8C%E8%A1%A8%28Hash%29\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#哈希表hash)

> [和为K的连续子数组\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/704c8388a82e42e58b7f5751ec943a11)

**问题简述**

```
给定一个无序数组 arr , 其中元素可正、可负、可0。给定一个整数 k ，求 arr 所有连续子数组中累加和为k的最长连续子数组长度。保证至少存在一个合法的连续子数组。
[1,2,3]的连续子数组有[1,2]，[2,3]，[1,2,3] ，但是[1,3]不是

要求：时间复杂度 O(n)，空间复杂度 O(n)
```

**思路：前缀和+哈希表**

* 记当前位置的前缀和为 `s`；
* 利用前缀和+哈希表，可以快速判断 `s - k` 是否存在；若存在表明有一组连续的子数组和为 `k`;
* 定义 `book = {s: i}` 表示最早在 `i` 位置出现前缀和为 `s`；
  * 比如 `arr = [1,1,-1,1]`，其中 `s[1] = 0` 而不是 `3`；
* 算法：

  ```python
  s = 0  # 前缀和
  for i in range(N):
      s += arr[i] 
      if s - k in book:
          if i - book[s - k] > mx_len:
              mx_len = i - book[s - k]
      if s not in book:  # 记录前缀和的最早位置
          book[s] = i
  ```
* Tips:
  * 初始化 `book` 时加入 `book[0] = -1` 兼容 `sum(arr[0:i]) == k` 的情况；
    * 比如 `arr = [1,2,3,6], k = 6`，遍历到 3 时，`book[6] = 2`，此时 `book[6-6] = book[0] = -1` 存在，更新最大长度为 `2 - (-1) = 3`

<details>

<summary><strong>Python</strong></summary>

```python
```

</details>