[LeetCode] 523. Continuous Subarray Sum

523. Continuous Subarray Sum

Medium

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

 

Constraints:

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

---

문제 풀이

• 연속 적인 부분 배열의 값이 k 의 배수로 나눠지는지 확인해야한다.
• 여기서 연속된 배열의 길이는 최소 2이다. 
• 그리고 k 의 배수 값은 항상 0 도 포함한다. 
• 제한을 보면 O(N) 으로 밖에 안풀릴 듯하다. 
• 해쉬 테이블을 사용해야한다. 
• 해쉬 테이블은 반목문에서 지금까지 더 해온 값에 k 를 모듈러 계산을 해주어 저장하는 키와, 현재 위치의 인덱스를 같이 넣는다. 
• 현재 위치까지의 총합을 k 로 나눈 나머지 값이 해쉬 테이블에 존재한다는 의미는, 그 값의 위치부터 현재 위치 까지의 합을 k 로 나눌 수 있다는 이야기다.
• 예를 들어 i 부터 k 로 나눴을때 나머지가 0 이라면, 처음 위치부터 i 까지의 총합을 k 로 나눈 나머지와 처음 위치부터 j 까지의 총합을 k 로 나눈 나머지 값과 같다.

소스 코드

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        hash_table = defaultdict()
        hash_table[0] = 0
        total = 0
        for i in range(len(nums)):
            total += nums[i]
            if total % k not in hash_table:
                hash_table[total % k] = i + 1
            elif hash_table[total % k] < i:
                return True
        return False