523. 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.

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

접근

#해시테이블 #부분합

단순히 Brute Force를 사용하면 시간초과가 나기 때문에, 해시테이블을 이용해 나머지를 저장하여 해결하였다.

부분합을 저장하는 변수 s와 해시 테이블 hash_map을 초기화하고, nums을 순회한다. 이 때 hash_map의 key는 s%k이고, value는 index+1이다.
s는 해당하는 nums[i]를 더하고, 그 값을 K로 나눈 나머지를 해시맵에서 검색한다. 해시맵에 존재하지 않는 값이라면 새로 추가한다.

이 때 s%k의 나머지는 새로 추가된 nums[i]의 합(즉, subarray의 합)이 k가 될 때마다 같은 값이 된다. 이를 이용해 해시맵에 같은 key가 존재하면 subarray의 합이 k가 되는 값이 존재한다고 판단하고 True를 리턴한다. 이때, subarray의 길이는 2보다 커야 하므로 value의 값은 현재 i값보다 작아야 한다.

for루프가 끝난 뒤에도 코드가 종료되지 않았다면, 조건에 해당하는 subarray가 없다고 보고 False를 리턴한다.

코드

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        hash_map = {0: 0}
        s = 0
        
        for i in range(len(nums)):
            s += nums[i]
            
            # s%k는 추가된 nums[i]의 합이(subarray의 합이) k와 같아질 때마다, 이전에 저장한 값의 나머지와 동일해진다.
            # 처음 발견된 s%k값을 i+1번으로 해시맵에 저장하고, 검색된 s%k의 value값이 현재 i값보다 작으면 위 조건을 만족한다 보고 True를 리턴한다.
            if s % k not in hash_map:
                hash_map[s % k] = i + 1
            elif hash_map[s % k] < i: # s%k가 해시맵에 존재하고, 그 값이 i보다 작으면(subarray의 길이가 최소 2면)
                return True

        return False

효율성

O(n)

Runtime: 2729 ms, faster than 13.97% of Python3 online submissions for Continuous Subarray Sum.
Memory Usage: 33.2 MB, less than 73.31% of Python3 online submissions for Continuous Subarray Sum.