動機

要與560一起看

Problem

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

 

Example 1:

Input: nums = [23,2,4,6,7], k = 6Output: trueExplanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6Output: trueExplanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input: nums = [23,2,6,4,7], k = 13Output: false

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= sum(nums[i]) <= 231 - 1
  • 1 <= k <= 231 - 1

Sol: 看是不是倍數

存連續和，之後就是一次一次試看有沒有k的倍數

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        ret = False
        sums = []
        cnt = 0
        nums = [0] + nums #[0,0],0
        # sum(nums[j:i]) = sums[:i] - sum[:j] - 
        for i in range(len(nums)):
            cnt += nums[i]
            if cnt == k and i > 1:
                return True
            for j in range(len(sums)):
                #print(i,j)
                if k == 0:
                    if (cnt - sums[j]) == 0:
                        #print((i-j) > 1)
                        ret = ret or (i-j) > 1
                elif (cnt - sums[j]) % k == 0:
                    #print((i-j) > 1)
                    ret = ret or (i-j) > 1 #not only this sol [23, 2, "6", 4, 7],  k=6
            sums.append(cnt)
            if ret :
                return True
        return False

Sol2: 取餘數

sum[j] - sum[i] = a[j] + ... + a[i+1] 如果是k的倍數都取餘會變成 sum[j]%k - sum[i]%k = 0

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        check = {}
        check[0] = -1
        
        pre_sum = 0
        for i,num in enumerate(nums):
            pre_sum += num
            if k != 0:
                pre_sum %= k
            if pre_sum in check: 
                if i - check[pre_sum] > 1:
                    return True
            else:
                check[pre_sum] = i
        
        return False