如何查找和为k的最长子数组？寻求优于O(n²)的高效解法

为什么滑动窗口不适用？ #

因为数组包含正负整数，窗口的和不具备单调性——扩大窗口可能让和变小，缩小窗口可能让和变大，没法像全正数数组那样通过调整左右边界来高效定位目标子数组。

更优解法：前缀和+哈希表 #

时间复杂度O(n)，空间复杂度O(n)，比暴力枚举的O(n²)高效得多。

核心思路

1. 前缀和定义：prefix[i] 表示数组前i个元素的累加和（规定prefix[0] = 0，对应空数组的和）。
2. 子数组和的转化：对于子数组arr[j+1...i]，它的和等于prefix[i] - prefix[j]。如果这个和等于k，那么等价于prefix[j] = prefix[i] - k。
3. 哈希表的作用：记录每个前缀和第一次出现的索引——因为要找最长子数组，相同的前缀和保留最早的索引，后续遇到时计算的i - j才会最大。

结合示例拆解

示例数组arr=[-20,-38,-4,-7,10,4]，k=3：

• 计算前缀和序列：[0, -20, -58, -62, -69, -59, -55]
• 当遍历到i=6（对应元素4）时，当前前缀和是-55，-55 - 3 = -58，而-58对应的最早索引是2，所以子数组长度为6-2=4，对应[-4,-7,10,4]，这就是最长的符合条件的子数组。
• 当遍历到i=5（对应元素10）时，当前前缀和是-59，-59 -3 = -62，对应索引3，子数组长度5-3=2，对应[-7,10]。

代码实现（Python）

def longest_subarray_sum_k(arr, k):
    prefix_map = {0: -1}  # 初始化：前缀和0对应索引-1，处理从数组开头就满足条件的情况
    current_sum = 0
    max_len = 0
    
    for idx, num in enumerate(arr):
        current_sum += num
        # 检查是否存在目标前缀和
        target = current_sum - k
        if target in prefix_map:
            current_len = idx - prefix_map[target]
            if current_len > max_len:
                max_len = current_len
        # 仅保存前缀和第一次出现的索引
        if current_sum not in prefix_map:
            prefix_map[current_sum] = idx
    return max_len

# 测试示例
arr = [-20,-38,-4,-7,10,4]
k = 3
print(longest_subarray_sum_k(arr, k))  # 输出4

注意事项

• 必须初始化prefix_map为{0: -1}，否则会漏掉从数组第一个元素开始就满足和为k的子数组。
• 不要更新哈希表中已存在的前缀和索引，因为更早的索引才能对应更长的子数组。

内容的提问来源于stack exchange，提问作者Anurag Tripathi