检查子数组和为target倍数的代码中判断条件为何为i-dic[summ]>=2
逻辑推导说明
这个解法基于前缀和同余性质:如果两个不同位置的前缀和对k取余结果相等,那么两个位置之间的连续子数组总和必然是k的倍数。
下标与长度的对应关系
代码里哈希表dic存储的是「余数第一次出现时对应的nums数组下标」,我们可以直接推导长度计算逻辑:
- 假设余数
r第一次出现在nums下标为pre_idx的位置,此时的前缀和对应nums[0] ~ nums[pre_idx]的总和 - 后续遍历到下标
cur_idx时再次出现相同余数r,此时的前缀和对应nums[0] ~ nums[cur_idx]的总和 - 两个前缀和的差值就是
nums[pre_idx+1] ~ nums[cur_idx]的总和,这个值是k的倍数,符合倍数要求 - 这段子数组的长度计算公式为:
cur_idx - (pre_idx + 1) + 1 = cur_idx - pre_idx,刚好等于两个下标的差值,不需要额外加1
为什么判断条件是>=2
题目明确要求子数组长度至少为2,因此需要cur_idx - pre_idx >= 2。如果条件改为>=1,会出现单元素子数组的误判,举个实际反例:
输入nums = [6, 1], k=6:
- 初始化
dic = {0: -1},前缀和初始值为0 - 遍历到
i=0(对应元素6),计算得前缀和模k结果为0,此时i - dic[0] = 0 - (-1) = 1,如果判断条件为>=1就会直接返回True,但此时对应的子数组只有[6],长度为1不符合要求。
我们也可以用合法用例验证规则的合理性:输入nums = [2,4], k=6,遍历到i=1时前缀和模k结果为0,1 - (-1) = 2,刚好对应长度为2的合法子数组[2,4],符合题目要求。
内容的提问来源于stack exchange,提问作者bloomsdayforever
相关产品推荐
相关产品推荐

