Saved from https://leetcode.com/problems/continuous-subarray-sum/submissions/

lc523

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        """
        Trick: remainder + n * k = some prefix sum (i...j)
             => (remainder + n * k) % k = some prefix sum (i...j) % k
             => remainder = some prefix sum (i...j) % k
         In other words:
            a % k = x
            b % k = x
            (a - b) % k = x -x = 0

         1) if remainder_j exist in the prefix sum array for the current sum_i, then it means prefix_sum_i and prefix_sum_j have the same remainder, 
         which means (prefix_sum_i - prefix_sum_j) % k == 0
         2) if remainder_j == 0, then it means prefix_sum_j % k == 0, which is also a valid case
        """
        
        curr_sum = 0
        # We ignore duplicate key, only store the first key is enough (since the question is asking for a boolean result)
        prefix_sum = {}
        for i in range(0, len(nums)):
            curr_sum += nums[i]
            remainder = curr_sum % k
            if i > 0 and remainder == 0:
                return True
            if remainder in prefix_sum:
                if i - prefix_sum[remainder] > 1:
                    return True
            else:
                prefix_sum[remainder] = i

        return False
    
    
    def improved_naive_solution(self, nums: List[int], k: int) -> bool:
        """
        Leverage a prefix sum array to avoid one for-loop
        Time: O(n^2)
        Space: O(n)
        """
        prefix_sum = list(accumulate(nums))
        for start in range(len(nums)):
            if start != 0 and prefix_sum[start] % k == 0:
                return True
            for end in range(start+2, len(nums)):  # end is inclusive
                if (prefix_sum[end] - prefix_sum[start]) % k == 0:
                    return True
        return False
            
        
    def naive_solution(self, nums: List[int], k: int) -> bool:
        """
        Enumerate every subarray (i, j) pair
        Time: O(n^3)
        Space: O(1)
        """
        for end in range(1, len(nums)):
            for start in range(0, end):
                curr_sum = sum(nums[start:end+1])
                if curr_sum % k == 0:
                    return True
        return False