###### tags: `Leetcode` `medium` `hash` `prefix sum` `python`

# 523. Continuous Subarray Sum

## [題目連結:] https://leetcode.com/problems/continuous-subarray-sum/

## 題目:
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 = 6
Output: true
Explanation: [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 = 6
Output: true
Explanation: [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 = 13
Output: false

## 解題想法:
* 連續子序列(長度>=2)總和能整除k
* 利用同餘概念
* a%c=x
* b%c=x
* (a-b)%c=**0**
* 用一個dic紀錄每次出現的餘數:
* **key:當前餘數**
* **val:當前餘數出現的位置**
* 若當前餘數已經出現在dic中且距離>1 return True

## Python:

class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        curMod=0
        dic={0:-1} #key:mod,val:pos
        for pos,val in enumerate(nums):
            #每次累加，取餘數
            curMod+=val
            curMod%=k
            if curMod in dic:
                #需大於1，ex: nums=[0],k=1這種極端case應為False
                if pos-dic[curMod]>1:
                    return True
            else:
                dic[curMod]=pos
        return False

if __name__ == '__main__':
    result=Solution()
    ans=result.checkSubarraySum(nums = [23,2,4,6,7], k = 6)
    print(ans)