523. Continuous Subarray Sum

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # time O(N^2) space O(N)
        # step1: initialize remainder: idx
        # edge case: when [0], k = 0 
        size = len(nums)
        # edge case
        if size < 2: return False 
        psum = [0] * size 
        psum[0] = nums[0]
        
        # get presum 
        for i in range(1,size):
            psum[i] = psum[i-1] + nums[i]
            
        # nums[i:j+1]    j - i >= 1 
        for i in range(size-1):
            for j in range(i+1,size):
                # num[i+1] + num[i+2] + .. +num[j]
                summ = psum[j] - psum[i] + nums[i] 
                if summ == k or (k != 0 and summ %k == 0):
                    return True
        return False 

class Solution:
    def checkSubarraySum(self, A: List[int], k: int) -> bool:
        # time O(N) space O(min(k,,N))
        # step1: initialize remainder: idx
        # edge case: when [0], k = 0 
        d = {0:-1}
        psum = 0 
        for i,a in enumerate(A):
            psum  += a 
            if k != 0: 
                psum = psum % k

            if psum in d:
                if(i-d[psum])> 1: # i - (j+1) >= 1  => i-j >= 2    
                    return True
            else: # only update d with current idx when psum not in  
                d[psum] = i
        return False