和为K的连续子数组

和为K的连续子数组_牛客题霸_牛客网

问题简述

给定一个无序数组 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；

• 算法：

  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

Python