560和为k的子数组

题目:给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
说明:数组的长度为 [1, 20,000]。
      数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。

1.枚举法

Time:O(n2) Space:O(1)
tip:数组元素范围中有负数,循环中间不可以提前结束。eg:[1,2]、[1,2,-1,1]

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

2.前缀和加哈希表优化

Time:O(n) Space:O(n)
定义pre[i]为[0..i]里所有数的和,pre[i]可以由pre[i−1] 递推而来,即:

pre[i] = pre[i−1] + nums[i]

那么[j..i] 这个子数组和为k,这个条件我们可以转化为

pre[i] − pre[j−1] == k

Hash表中存储<和,出现次数>,pre[i]和pre[j-1]可以直接从hash表中获得,时间复杂度是O(1)

//Java
public class Solution{
    public int subarraySum(int[] nums,int k){
        HashMap<Integer,Integer> map = new HashMap<>();
        int pre = 0,count = 0;  
        map.put(0,1);
        for(int i = 0;i < nums.length();++ i){
            pre += nums[i];
            if(map.containsKey(pre-k)){
                count += mp.get(pre-k);
            map.put(count,mp.getOrDefault(pre, 0) + 1);
            }
        return count; 
        }      
    }
}


上一篇:560. 和为K的子数组


下一篇:560.和为k的子数组