Longest Subarray with Sum K
给定整数 nums 和目标值 k，返回元素之和恰好为 k 的最长子数组的长度。子数组是一段连续的元素，长度至少为 1。某些值可能为 0 或负数。如果没有子数组的元素之和为 k，则返回 0。
函数
- numsinteger-array
- 要搜索的整数，包括负数和零
- kinteger
- 子数组必须具有的确切总和
- 返回值integer
- 和为 k 的最长子数组的长度；如果不存在这样的子数组，则为 0
约束条件
1 ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104-109 ≤ k ≤ 109- 每个前缀和都保持在
-2 × 108和2 × 108之间，因此 32 位整数就足够了。 - 如果没有任何子数组的和等于
k，则返回0。
示例
- 输入
- nums = [2, -1, 3, 1, -4, 2, 3]k = 5
- 输出
- 5
- 解释
- 三段连续区间的和都是 5：最后一个是
[2, 3]，第一个是[2, -1, 3, 1]，还有一个位于索引 2 到 6 的[3, 1, -4, 2, 3]。最后一个最长，有 5 个元素。
- 输入
- nums = [4, 1, 1, 2, -1, 1]k = 3
- 输出
- 4
- 解释
- 索引 1 到 4 处的
[1, 1, 2, -1]和索引 2 到 5 处的[1, 2, -1, 1]都由 4 个元素组成，元素之和都是 3。你要返回的是长度，因此平局无关紧要。
- 输入
- nums = [-3, 6, -3]k = 1
- 输出
- 0
- 解释
- 6 个子数组的和分别是 -3、6、-3、3、3 和 0。它们都不是 1，所以答案是 0。
进阶
如果仍允许出现负值，你会如何找到和不超过 k 的最长子数组？
提示
逐个打开提示，每个都会多透露一点。
有 20,000 个数字时，暴力法需要累加约 2 × 10^8 个起点和终点对。负数也会让滑动窗口失效：总和超过
k的一段数，之后可能又降到k。记录哪个累计总和，能让你通过一次减法求出任意子数组的和？使用累积前缀和时，位置
i之后到位置j的元素之和为prefix[j] - prefix[i]。如果某个更早的前缀和等于prefix[j] - k，那么以j结尾的子数组之和就是k。如果有多个更早的前缀和符合条件，哪个能得到最长的子数组？对于每个运行总和，记录它首次出现的索引，从索引 -1 处的总和 0 开始。在每个索引处，查找
prefix - k，并将距离与你的最佳长度进行比较。只有当当前前缀不在映射中时，才将它添加到映射中。
题解
累计和可以把任意子数组的和转化为一次减法：索引 s 之后到索引 i 的元素之和为 prefix[i] - prefix[s]。记住每个累计和首次出现的索引，然后只需遍历一次，就能找到每个位置结束的最长匹配子数组。
从每个起点扩展每个子数组
结果正确，但无法在最大的测试中运行完毕
思路
从每个起点开始向右延伸，把每个元素加到当前总和中。每当总和等于 k 时，就记录长度。每个子数组都对应一对起点和终点，因此不会遗漏。即使总和超过 k，也要继续延伸：第一个示例中从索引 2 开始，总和依次为 3、4、0、2、5，其中的 -4 就是最后一个总和达到 5 的原因。
大约有 n²/2 对：当 n = 2 × 10^4 时，需要进行 2 × 10^8 次加法。
算法
- 将
best设为 0。 - 对于每个
start，将total设为 0。 - 将
end从start移动到最后一个索引，并将nums[end]加到total中。 - 当
total等于k时，将best设为best和end - start + 1中较大的值。 - 返回
best。
def longestSubarrayWithSumK(nums, k):
n = len(nums)
best = 0
for start in range(n):
total = 0
for end in range(start, n):
total += nums[end]
# A match may come after the total has passed k, so never stop early
if total == k and end - start + 1 > best:
best = end - start + 1
return best为每个和添加第一个索引的前缀和
思路
当某个以索引 i 结尾的连续区间总和为 k 时，恰好有某个更早的总和等于 prefix - k。如果有多个更早的总和符合条件，最早出现的那个会作为最长区间的起点，因此映射中只在某个总和首次出现时存储它。之后再次出现的相同总和只能作为更短区间的起点。将总和 0 存入映射，并设索引为 -1，这样从索引 0 开始的匹配区间长度就是 i + 1。
第一个示例中的总和依次为 2、1、4、5、1、3、6。在索引 6 处，6 - 5 = 1，它首次出现在索引 1 处，因此区间长度为 5。总和 1 在索引 4 处再次出现，而保留索引 1 才能找到这个区间。
每个元素只需查找一次，因此时间复杂度为 O(n)，映射最多存储 n + 1 个总和。
算法
- 创建一个映射表
first，在索引 -1 处存储总和 0，并将prefix和best设为 0。 - 对于每个索引
i，将nums[i]加到prefix上。 - 如果映射表中索引
start处的值是prefix - k，则将best设为best和i - start中较大的值。 - 如果映射表中还没有
prefix，则将它与索引i一起存入映射表。 - 返回
best。
def longestSubarrayWithSumK(nums, k):
# first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
first = {0: -1}
prefix = 0
best = 0
for i, num in enumerate(nums):
prefix += num
# The earliest prefix equal to prefix - k starts the longest match that ends at i
start = first.get(prefix - k)
if start is not None and i - start > best:
best = i - start
# Keep the first index only: a later one could only start a shorter subarray
if prefix not in first:
first[prefix] = i
return best
易错点和边界情况
- 每次总和重复时，都覆盖已存储的索引，这样可以保留最新的起始位置，并找到更短的匹配结果。第一个示例返回 4 而不是 5，因为总和 1 的索引从 1 移到了 4。
- 当窗口的总和大于
k时缩小窗口，第一个示例也会返回 4。窗口最终包含[-1, 3, 1, -4, 2, 3]，总和为 4，而且不会移除 -1。 - 如果不记录索引 -1 处的总和 0，就会漏掉所有从索引 0 开始的匹配结果：
[5, 0, 0, 0]在k = 5时返回 0，而不是 4。 - 存储的索引是子数组之前的位置，因此长度为
i - start。加上 1 会多算一个元素。
常见问题3
和为 K 的最长子数组的时间复杂度是多少？
使用运行总和和首个索引映射，时间复杂度为 O(n)，额外空间复杂度为 O(n)：每个元素只需查找一次，最多插入一次。从每个起点扩展所有子数组，需要 O(n²) 时间和 O(1) 空间。
为什么数组中有负数时，滑动窗口会失效？
滑动窗口假设加入一个元素会使总和增大，移除一个元素会使总和减小。存在负数时，总和过大的窗口在加入一个负数后仍可能达到 k，而总和过小的窗口可能需要移除左侧的负数。窗口无法判断哪种操作才是正确的。
和为 K 的最长子数组问题能否用 O(1) 的额外空间解决？
只有在没有负值时才适用。这样，随着窗口扩大，总和不会下降，双指针就能在 O(n) 时间和 O(1) 空间内找到总和为 k 的最长窗口。如果有负值，你就需要使用总和映射，或者进行 O(n²) 扫描。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def longestSubarrayWithSumK(nums, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [2, -1, 3, 1, -4, 2, 3] k = 5
预期输出
5