和为k的子数组--.py

"""
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。


“前缀和”听起来很高大上，其实就是将数组中的值累计加起来。比如对于[1,1,1]，它的前缀和就是[1,2,3]；再比如对于[1,2,3]，前缀和就是[1,3,6]。
因此对于题目中给的数组nums，我们就先拿到它所对应的前缀和。拿到之后有什么用呢？通过前缀和，我们看似只能得到从头开始的和，无法得到中间某一部分的和——但其实不然。
比如对于数组[1,2,3]，我们想得到2与3的和5，只需要用前缀和的第3位（6）减去 前缀和的第1位（1），不就可以得到了吗。即通过前缀和的第m位减去前缀和的第n位，就可以得到n到m之间的子数组的和。就是这个结论后面要用。
现在，只要我们利用好前缀和的这个性质，就可以涵盖到数组中所有子数组并进行判断和计数了。

具体思路就是：我们定义一个计数字典count，这个count记录下数组中所有前缀和的值以及对应个数。我们从头开始遍历数组，遍历的同时计算前缀和，将每一个前缀和都保存在count中。如果到哪一步前缀和直接等于k，
      说明直接找到了一个从头开始加出来的和为k的子数组，结果数+1；除此之外，如果到哪一步，此时的前缀和-k在count中（即等于之前的某个前缀和），那么说明这两个前缀和之间的数组就是和为k的！这就对应着上
      面提到的要用的结论，只不过形式上有些变化。

举个例子，还是对于[1,2,3]，我们的k是5。现在我们有前缀和[1,3,6]，遍历到6了，我们发现6-5=1 在前缀和记录count字典中，因此我们就找到了这么一个和为5的子数组。

有些时候，我们得到了此时的前缀和-k是之前出现过的旧前缀和，这个旧前缀和出现的个数可能不止一个（因为可能几个不同位置上的前缀和都是一样的），那么有几个旧前缀和，我们就加几个结果——因为这些不同的
     位置都可以分别和当前前缀和的位置组成不同的子数组。


利用前缀和   要把看似没用的保留下来 利用字典
字第里面是{前缀和，前缀和的次数}
[1,0,2,1,1]  2
例如到索引为2  此时数字为2  和为3  减去k=2  前面的和为1的次数就是2


思想就是 我知道前1 2 3 4 5 。。。 n的和（n个数）   现在知道前m（m>n)的和
    如果前m的和 减去 k得到的数 在前面的n的和（n个数）里面存在j个（假设有一个是前4项的和）  那就对应的有
    j个连续数组(其中一个是[5:m])的和为k
"""
def slove(nums,k):
    total_sum = 0
    dic = {0:1}
    result= 0
    for num in nums:
        total_sum+=num
        result += dic.get(total_sum-k,0)
        dic[total_sum] = dic.get(total_sum,0)+1
    print(dic)
    return result

print(slove([1,1,1,2], 3))