523. Continuous Subarray Sum (Array, Hash Table, Math, Prefix Sum)

링크 - https://leetcode.com/problems/continuous-subarray-sum/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 현재 mod값을 통해 one pass로 문제를 풀 수 있다. 먼저 매 nums마다 mod값을 변경해주고, 만약 봤던 mod가 해시테이블에 있으면, 우리는 그 값들 사이에 good subarray가 있다는 뜻이므로 True를 반환한다.

Code

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        curr_mod = 0
        hash_table = {0: -1}

        for i in range(len(nums)):
            curr_mod = (curr_mod + nums[i]) % k
            if curr_mod in hash_table:
                if i - hash_table[curr_mod] > 1:
                    return True
            else:
                hash_table[curr_mod] = i

        return False

Complexity

Time Complexity: O(N)

Space Complexity: O(N)