560. Subarray Sum Equals K

[tech-cow]

560. Subarray Sum Equals K

'''
不懂的可以参考: https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/hot-100-he-wei-kde-zi-shu-zu-python3-cong-bao-li-j/
[1:29] Start

Thought Process
1. [Brute Force]

for i -> n
    for j -> (i, n)
        find sum of nums[i:j + 1] == target

Time: O(N^3)


2. PreSum

for i -> n
    preSum = [0] * len(arr)
    for j -> (i, n):
        if preSum[j] - preSum[i] == k
            add to res

Time: O(N^2)


3. preSum

because: preSum[j] - preSum[i] == k

so: preSum[i] == preSum[j] - k

because we always iterate i before j
we store preSum[i] in hash
and while we iterate J, we do preSum[j] - k, and see if it's in hash.

Time: O(N)

'''

# preSum + O(N^2)
class Solution(object):
    def subarraySum(self, nums, target):
        if not nums: return 0
        n = len(nums)
        res = 0
        for i in range(n):
            preSum = 0
            for j in range(i, n):
                preSum += nums[j]
                if preSum == target:
                    res += 1
        return res

# preSum + hash O(N)
class Solution(object):
    def subarraySum(self, nums, target):
        if not nums: return 0
        dic = {0 : 1}
        preSum = 0
        res = 0
        for i in range(len(nums)):
            preSum += nums[i]
            if preSum - target in dic:
               res += dic[preSum - target]
            dic[preSum] = dic.get(preSum, 0) + 1   
        return res

[tech-cow]

class Solution(object):
    def subarraySum(self, nums, k):
        res = 0
        n = len(nums)
        for i in range(n):
            preSum = 0
            for j in range(i, n):
                preSum += nums[j]
                if preSum == k:
                    res += 1
        return res

class Solution(object):
    def subarraySum(self, nums, k):
        dic = {0 : 1}
        n = len(nums)
        preSum = 0
        res = 0
        for i in range(n):
            preSum += nums[i]
            if preSum - k in dic:
                res += dic[preSum - k]        
            dic[preSum] = dic.get(preSum, 0) + 1
                
        return res