刷题一时爽，一直刷题一时爽。
终于知道哈希是什么了。

1.题目

原题

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

例子

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

2.解析

思路1：还是双指针，但是讨论了一番以后，发现不能解决从0开始的数组之和小于目标值情况。
想想还是算了。
思路2：哈希表，建一个字典，这个字典存的东西是到第i个数的和。考虑这样一个性质，如果到第j个数的和减到第i个数的和得到的值为k，那么这个i到j的连续子数组和肯定为K。定义一个字典，key为累积和，value为累积和出现的次数，这样所有的连续数组都可以找到了。

3.python代码

##双指针法，这个有个情况解决不了，但思路还是挺好的
    def subarraySum(self, nums, k):
        start, end = 0, 0
        count = 0
        tmpsum = nums[0]
        m = len(nums)
        while start < m and end < m:
            print(start, end, tmpsum)
            if tmpsum == k:
                count += 1
                if start < m - 1:
                    start += 1
                    end = start
                    tmpsum = nums[start]
                else:
                    break
            elif tmpsum > k:
                tmpsum = tmpsum - nums[start]
                start += 1
            else:
                if end < m-1:
                    end += 1
                    tmpsum = tmpsum + nums[end]
                else:
                    break
        return count
##归纳法
    def subarraySum(self, nums, k):
        d = {0: 1}
        m = len(nums)
        sumk = 0
        res = 0
        for i in range(m):
            sumk += nums[i]
            if sumk - k in d:
                res += d[sumk - k]
            if sumk in d:
                d[sumk] += 1
            else:
                d[sumk] = 1
        return res