[Leetcode] 523. Continuous Subarray Sum

문제

 

https://leetcode.com/problems/continuous-subarray-sum/description/

Continuous Subarray Sum - LeetCode

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	Output
nums = [23,2,4,6,7], k = 6	true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

 

Example 2:

Input	Output
nums = [23,2,6,4,7], k = 6	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	Output
Input: nums = [23,2,6,4,7], k = 13	false

 

 

문제풀이 코드

첫번째 풀이

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

첫번째로 풀때는 무식하게 이중 for문을 돌려서 풀었는데, 당연하게도 시간초과로 해결되지 않았다...

 

 

두번째 풀이

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        _sum, dic = 0, {0:-1}
        for idx, num in enumerate(nums):
            # k현재까지 합계의 나머지
            _sum = (_sum + num) % k
            # 같은 나머지가 나온다면 이전에 나왔던 위치에서 현재까지 k의 배수가 더해진 것
            # 같은 나머지가 존재하는 위치가 현재 위치와 거리가 2이상이 되어야함:
            if _sum not in dic:
                dic[_sum] = idx
            elif idx - dic[_sum] >= 2:
                return True
        return False

딕셔너리(Hash Table)를 이용한 풀이

1. 나머지의 인덱스와 합계를 선언

2. 현재 위치까지의 합계의 나머지를 구한다.

3. 현재 위치까지의 합계의 나머지가 딕셔너리에 들어가있다면 현재 위치의 값에서 딕셔너리의 값을 뺀 값이 2이상일 때 True를 반환하고

4. 나머지가 딕셔너리에 들어가있지 않으면 값을 넣어준다

5. 반복문이 종료되면 False를 반환한다