010和为k的子数组个数---2022/03/23

题目描述解题思考代码实现性能评估

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

版本一：使用双层遍历，找到合适的子数组就存起来，否则继续遍历。缺陷：超出时间限制。（或者前缀和相减，但是时间复杂度是一样的）

版本二：对于数组双层遍历的优化方向主要在使用左右指针，但是自己对于在不同判断条件下的使用没有很好的处理，导致使用起来还是会出现对于子数组错判或者漏判的情况。在本题中，需要注意：
1、题目说的是整数数组，说明数组中是既有正数也有负数，这样的话，使用滑动窗口不是一个明智的选择；
2、参考其他大牛的思路，如果出现正负混杂的数做求和的情况，推荐使用前缀和+哈希表。具体思路：遍历所有前缀和，遍历的同时判断，前缀和表中是否包含当前前缀和-k的值，如果包含，将其出现次数加到计数中，否则就记录当前的前缀和次数加1。

收获：
1、对于滑动窗口的使用有了更进一步的了解，添加当前右指针的数进去之后，先做判断，是否大于k且r>l，大于的话要先滑动左指针，而后再判断是否等于k，再做计数。我在一开始做的时候，先计数后做判断，导致出现漏数或多数的情况。

python代码如下：（目前暂未找到可以直接使用的HashTable），所以还需要自己实现哈希表这个类？

def subarraySum( nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        cnt=0
        sum=0
        preSum=HashTable()
        preSum.add(0,1)
        for n in nums:
            sum+=n
            if preSum.contaiKey(sum-k):
                cnt+=preSum.get(sum-k)
            preSum.add(sum,preSum.getOrDefault(sum,0)+1)
        return cnt

以下为Java代码：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int cnt=0,sum=0;
    	Map preSum=new HashMap<>();
    	preSum.put(0, 1);
    	for(int n :nums) {
    		sum+=n;
    		if(preSum.containsKey(sum-k)) {
    			cnt+=preSum.get(sum-k);
    		}
    		preSum.put(sum, preSum.getOrDefault(sum, 0)+1);
    	}
		return cnt;

    }
}

心得：看题看得飞快，做题也做得飞快，但是实际提交问题却不少，一遍遍优化花费更多的时间，那么下一次是否可以多考虑一种可能？？？
充满欣喜的绝对不是我会做，而是原来还可以这样做。一步一步积累吧。欲速则不达，心急吃不了热豆腐。