Leetcode Hot 100 & 560. Subarray Sum Equals K

　　参考资料：

　　考点：子串 & [题干]

1 Input: nums = [1,1,1], k = 2
2 Output: 2

　　这道题说实话看得我一脸懵，第一时间想到的自然是双层循环遍历的一个$O(n^2)$的解法，也就是官方的解法一。但是使用这种解法会超时（Python语言是这样的，评论区有人提到了），我知道会扑该所以直接不写了，然后思索了半天还是没有好的思路，就直接看解答了。

　　解答二说实话蕴含了非常牛逼的思想（以空间换时间，hash表），这个解法我觉得如果初见这题的人能在一天之内想到，我都会佩服的五体投地。太精致巧妙了！并且一同百通，对于子串这个考点是非常好的例子。

　　1. 对解答二的理解

　　解答二蕴含了一个（让人拍大腿，懊悔自己为啥没想到的）基本的思路，即连续的子串和实际上等于两个前缀子串和的差。两个前缀子串[1, 2, 3]和[1, 2, 3, 4, 5]，可以推出子串[4, 5]的和是9。此时我们反其道而行之，如果k = 9，当我们遍历到5时，即pre_sum[4] = 1 + 2 + ... + 5 = 15，我们计算pre_sum[4] - k = 6，则如果[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]的前缀和里面有6，那么岂不美哉，正正好好对上了！下面是我自己的Python实现，官方解法没有给python语言，我自己写了代码但是超时了。。。用了别人的代码可以过，感觉像是他的代码效率更高。。。不懂为啥，别人的：

 1 class Solution(object):
 2     def subarraySum(self, nums, k):
 3         """
 4         :type nums: List[int]
 5         :type k: int
 6         :rtype: int
 7         """
 8         d={0:1} ; 
 9         he = ans = 0
10         for v in nums:
11             he  += v
12             ans += d.get(he-k ,0)
13             d[he] = d.get(he,0) + 1
14         return ans

　　我写的：

 1 class Solution(object):
 2     def subarraySum(self, nums, k):
 3         """
 4         :type nums: List[int]
 5         :type k: int
 6         :rtype: int
 7         """
 8 
 9         n = len(nums)
10 
11         pre_sum_count = {}
12         pre_sum_count[0] = 1
13 
14         pre_sum = 0
15         count = 0
16         for i in range(n):
17             pre_sum += nums[i]
18             if pre_sum - k in pre_sum_count.keys():
19                 count += pre_sum_count[pre_sum - k]
20             
21             if pre_sum not in pre_sum_count.keys():
22                 pre_sum_count[pre_sum] = 1
23             else:
24                 pre_sum_count[pre_sum] += 1
25 
26         return count

　　可能是多了很多 in 的判断。。。但是为什么用get就不会有这个问题。。。anyway，又学会了一个get(XX, 0)，即获取key=XX的值，不存在则返回0，多学了一招喔。

　　收获：

1. 空间换时间的思想
2. 使用hash散列表代替数组做存储器的思想。人话：数组的索引是非负整数，很多时候有局限性，此时需要用到hash表，在python中对应的实现就是dict