Python solution with detailed explanation


  • 0
    G

    Solution

    Continuous Subarray Sum https://leetcode.com/problems/continuous-subarray-sum/?tab=Description

    • b-a = n * k => b = (a + n * k) => b%k = a%k
    • We build a cdf array and if any two members mod k is same or a member mod k is zero and idx > 1, we return True
    class Solution(object):
        def checkSubarraySum(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: bool
            """
            k = abs(k)
            if len(nums) < 2:
                return False
            if k == 0 and sum(nums) > 0:
                return False
            if k == 0 and sum(nums) == 0:
                return len(nums) >= 2
            cdf = [0]
            for x in nums:
                cdf.append(x+cdf[-1])
            y  = set([])
            for idx,x in enumerate(cdf):
                if idx == 0:
                    continue
                if x % k in y or x%k == 0 and idx > 1:
                    return True
                y.add(x%k)
            return False
    

  • 0
    M

    Try
    [1,0,0,1]
    0


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.