哈希算法题目：连续子数组和

题目描述
给定一个包含非负整数的数组 nums 和一个整数 k，请判断该数组是否存在一个连续的子数组，其长度至少为 2，且元素总和是 k 的整数倍。如果存在，返回 true；否则，返回 false。

示例

输入：nums = [23, 2, 4, 6, 7], k = 6
输出：true
解释：子数组 [2, 4] 的元素总和为 6，是 6 的整数倍。

解题过程

第一步：理解题意
题目要求我们找到一个长度至少为 2 的连续子数组，使其元素之和能被 k 整除。
换句话说，如果我们用 sum[i] 表示从数组开头到第 i 个元素（索引从 0 开始）的累加和，那么子数组 nums[i+1..j] 的和是 sum[j] - sum[i]。我们需要满足：

\[(sum[j] - sum[i]) \mod k = 0 \]

即：

\[sum[j] \mod k = sum[i] \mod k \]

注意，这里要求子数组长度至少为 2，即 j - i >= 2，也就是 j - i >= 1 在索引差上对应至少差 2 个位置。

第二步：转化思路
根据上述推导，我们可以：

1. 遍历数组，计算到当前位置的累加和 prefix_sum。
2. 计算 prefix_sum % k 的余数。
3. 如果这个余数之前已经出现过，且当前索引与之前出现同一余数的索引至少相差 2（保证子数组长度 ≥ 2），则返回 true。
4. 如果没出现过，则将当前余数及其索引存入哈希表。
5. 特别注意：如果 k == 0，则判断条件变成 sum[j] == sum[i]，即两个前缀和相等。

第三步：处理边界情况

1. 数组长度小于 2：直接返回 false。
2. k 可能为 0：此时判断子数组和是否为 0，即 sum[j] == sum[i]。
3. 负数？题目说非负整数，所以不需要处理负数取模的歧义，但要注意在编程语言中，负数取模结果可能为负，不过本题无负数。
4. 子数组长度至少为 2 的索引判断要小心。

第四步：逐步推导示例
数组：[23, 2, 4, 6, 7], k = 6

• 初始化哈希表 map，键为余数，值为第一次出现该余数的索引。
• 预先在哈希表中存入 {0: -1}，表示前缀和 0 出现在索引 -1 的位置，方便处理从开头开始的子数组。
• 遍历过程：

1. i = 0, num = 23
   前缀和 = 23, 余数 = 23 % 6 = 5
   哈希表中无 5，存入 {0:-1, 5:0}

2. i = 1, num = 2
   前缀和 = 25, 余数 = 25 % 6 = 1
   哈希表中无 1，存入 {0:-1, 5:0, 1:1}

3. i = 2, num = 4
   前缀和 = 29, 余数 = 29 % 6 = 5
   哈希表中有 5，索引为 0，当前索引 2 与 0 相差 2（子数组长度为 2），满足条件，返回 true。

第五步：算法步骤整理

1. 如果数组长度 < 2，返回 false。
2. 创建哈希表 remainder_map，初始存入 {0: -1}。
3. 初始化 prefix_sum = 0。
4. 遍历数组，索引从 0 到 n-1：
   • prefix_sum += nums[i]
   • 如果 k != 0，remainder = prefix_sum % k，否则 remainder = prefix_sum。
   • 如果哈希表中已有这个 remainder：
     • 检查当前索引与哈希表中的索引差是否 ≥ 2，如果是则返回 true。
   • 否则，将 (remainder, 当前索引) 存入哈希表。
5. 遍历结束，返回 false。

第六步：复杂度分析

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(min(n, k))，哈希表最多存储 min(n, k) 个不同的余数。

第七步：代码实现（Python示例）

def checkSubarraySum(nums, k):
    n = len(nums)
    if n < 2:
        return False
    
    remainder_map = {0: -1}  # 余数 0 首次出现在索引 -1
    prefix_sum = 0
    
    for i in range(n):
        prefix_sum += nums[i]
        if k != 0:
            remainder = prefix_sum % k
        else:
            remainder = prefix_sum
        
        if remainder in remainder_map:
            if i - remainder_map[remainder] >= 2:
                return True
        else:
            remainder_map[remainder] = i
    
    return False

第八步：验证示例
输入：nums = [23, 2, 4, 6, 7], k = 6
执行过程如上推导，在 i=2 时返回 true。