LC523. Continuous Subarray Sum

Approach 1: Optimal

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # Edge case: if first element itself is divisible by k,
        # we don't want to return True since we need at least two
        # elements.
        remainders = { 0: -1 }
        total = 0
 
        for i, num in enumerate(nums):
            total += num
            rem = total % k
 
            if rem not in remainders:
                remainders[rem] = i
            elif i - remainders[rem] > 1:
                return True
 
        return False

Complexity

Time: $O(n)$
Space: $O(n)$

Notes

We keep tracking of the running sum in total and we keep track of the remainders in a hash map from dividing this sum at each point with k. The idea is that if we ever get a remainder that we already saw before, we have a good subarray by taking the range $[remainders[remainder]+1,i]$.

Other Languages