560. Subarray Sum Equals K

今天早上醒来突然想起来前年trans的时候被问到的一道题，求和为0的子数组，搜索lc发现了一道类似的题。
社招的时候大家其实也就没有校招的时候那么大的宽容度，所以基础题一定要OK，才有资格去argue合适的薪水。此外，既然吃了这碗饭，面试和工作中总会遇到这样的题，那么很有必要将这一关攻破。
从自己做面试官的经验来看，能做出算法题加能说清楚项目，再展现踏实的态度，国内公司应该基本都可以进了。此外展现问题的理解深度和沟通/带人/文档展现等能力影响的就是级别问题。

话不多说，首先是最原始的暴力解法，两层循环搜索。显然时间复杂度太高，过不了OJ

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        length = len(nums)
        if length == 0:
            return 0
        
        result = 0
        for i in range(length):
            merge = nums[i]
            if merge == k:
                result += 1
            for j in range(i+1, length):
                merge += nums[j]
                if merge == k:
                    result += 1
        return result
        

累加和数组的思路(复杂度没有降低，仍然过不了OJ)

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        sums = nums
        for i in range(1, len(nums)):
            sums[i] = sums[i-1] + nums[i]
        
        result = 0
        for i in range(len(sums)):
            if sums[i] == k:
                result += 1
            for j in range(i-1, -1, -1):
                if sums[i] - sums[j] == k:
                    # print('i,j,sums[i],sums[j]',i,j,sums[i],sums[j])
                    result += 1
        return result

第三种解法，用哈希表维护一个累加和的key-value的dict，key是累加和，value是累加和出现的次数。
本质上，子数组的和就是从0开始的两个数组的差，理解这一点就不难理解下面的方法。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        sums = 0
        tmp = {0:1}
        result = 0
        for i in range(0, len(nums)):
            sums += nums[i]
            if sums-k in tmp:
                result += tmp[sums-k]
            if sums in tmp:
                tmp[sums] += 1
            else:
                tmp[sums] = 1
        return result
                
            
            
        
        
        return result