Leetcode 0523 Continuous Subarray Sum

Problem statement

https://leetcode.com/problems/continuous-subarray-sum/

Solution

Evaluate cumulative sums, and check if we have two of them with the same reminder of division by k.

Complexity

Space complexity is O(k), time complexity is O(n).

Code

class Solution:
    def checkSubarraySum(self, nums, k):
        d = defaultdict(list)
        for i, sm in enumerate([0] + list(accumulate(nums))):
            d[sm % k] += [i]
            
        for val in d:
            if d[val][-1] - d[val][0] >= 2: return True
        return False