MUYANG GUO / INDEX

LeetCode

LeetCode 523 Continuous Subarray Sum - Medium

523. Continuous Subarray Sum -- Medium

·1 min read·#LeetCode#Medium#Python

523. Continuous Subarray Sum — Medium

Open on LeetCode

Problem

  1. Continuous Subarray Sum -- Medium

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6. Example 2:

Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Constraints:

The length of the array won't exceed 10,000. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Solution

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        #cur calculate the prefix sum remainder of input array A
        #seen will record the first occurrence of the remainder.
        #If we have seen the same remainder before,
        #it means the subarray sum if a multiple of k
        mapping = {0:-1}# mark the start
        prefix = 0
        for i, num in enumerate(nums):
            prefix += num
            key = (prefix % abs(k)) if k else prefix
            if key not in mapping:
                mapping[key] = i
            elif i - mapping[key] > 1:#at least 2
                return True
        return False

Comments