523. Continuous Subarray Sum - cocoder39/coco39_LC GitHub Wiki

523. Continuous Subarray Sum

2024

time O(N), space 0(min(N,k)) where N is len(mums). This is because the reminder hashmap can no more than k elements.

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        sum = 0
        reminders = {}
        for i, num in enumerate(nums):
            sum += num
            reminder = sum % k
            if reminder == 0 and i > 0:
                return True
            if reminder in reminders:
                if i - reminders[reminder] > 1: # length >= 2
                    return True
            else:
                reminders[reminder] = i
        return False

or add a dummy reminder {0:-1} to hashmap to normalize the process

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        prefix_sum = 0
        reminders = {0: -1}
        for i in range(n):
            prefix_sum += nums[i]
            
            if k != 0:
                prefix_sum = prefix_sum % k
            if prefix_sum in reminders:
                if i - reminders[prefix_sum] > 1:
                    return True
            else:
                reminders[prefix_sum] = i

        return False

First idea was purely prefix sum, which takes O(N ^ 2) time complexity. A better approach is to use hash map, similar to 2-sum except that we use reminder as map key. Also need to deal with input like [0,0,0] and k=0

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        prefix_sum = [0] * n
        for i in range(n):
            if i == 0:
                prefix_sum[i] = nums[0]
            else:
                prefix_sum[i] = nums[i] + prefix_sum[i-1]
        
        
        for i in range(n):
            for j in range(i+1, n):
                c = prefix_sum[j] - (prefix_sum[i-1] if i >= 1 else 0)
                if c == k or (k != 0 and c % k == 0):
                    return True
        return False