leetcode 523. 连续的子数组和

发表于 分类于 阅读次数：

解题思路

定义pre[i]

下标[0, i]的子数组和

求解方法

下标[j, i]的子数组和为k的倍数 (j<i)
<=>
pre[i]-pre[j-1] == n*k
<==>
pre[i] == n1*k + rem1
pre[j] == n2*k + rem2
rem1 == rem2
<==>
通过计算第i个元素前，是否有pre%k等于pre[i]%k，即说明存在以i结尾的子数组和为k的倍数

时间复杂度

O(n)

空间复杂度

O(min(n,k))

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        rem_to_index = {0: -1}  # 确保[0, i]子数组和是k的倍数时，返回true（i>=2）
        pre_sum = 0

        for i, num in enumerate(nums):
            pre_sum += num
            rem = pre_sum%k
            equal_rem_pos = rem_to_index.get(rem)

            if equal_rem_pos is None:
                rem_to_index[rem] = i
                continue

            if i - equal_rem_pos >= 2:
                return True
        
        return False