Continuous Subarray Sum

Problem Id: 523 Difficulty: Medium


Intuition

Solution


class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # Edge Cases
        if not nums:
            return False
        if k < 0:
            k = abs(k)
        if k == 0:
            for i, j in zip(nums[:-1], nums[1:]):
                if i == 0 and j == 0:
                    return True
            return False

        # dp solution
        visited = {}
        s = 0
        for i, num in enumerate(nums):
            s += num
            key = s % k
            if key == 0:
                if i > 0:
                    return True
                continue
            if key not in visited:
                visited[key] = i
            if key in visited and i - visited[key] >= 2:
                return True
        return False