[LeetCode] 523 | Continuous Subarray Sum | Python

---

문제 링크: 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.

---

조건

• 1 <= nums.length <= $10^5$
• 0 <= nums[i] <= $10^9$
• 0 <= sum(nums[i]) <=$2^{31}-1$
• 1 <= k <= $2^{31}-1$

---

내 풀이

나머지(modulo)의 특성 중 (a+b)%k = (a%k) + (b%k)와 같다는 것을 이용한다.

 

sums는 {합의 modulo: index}를 저장하는 dictionary로 사용한다.

현재(idx)까지 수의 합(cur_sum)을 구해서 그것의 나머지가 이미 sums안에 존재한다면 {cur_sum%k: i}, i부터 idx까지의 합이 k의 배수가 된다.

---

---

---

---

코드

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