leetcode热题(一)子串

和为k的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
示例 2：

输入：nums = [1,2,3], k = 3
输出：2
提示：

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
Related Topics
数组
哈希表
前缀和

暴力解法:

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res=0;
        for(int i=0;i<nums.length;i++)
        {
            int sum=0;
            for(int end=i;end>=0;end--){
                sum+=nums[end];
                if(sum==k)
                    res++;
            }
        }
    return res;
    }
}

前缀和解法

class Solution {
    public int subarraySum(int[] nums, int k) {
        int len=nums.length;
       int []presum=new int[len+1];
       presum[0]=0;
       for(int i=0;i<len;i++){
           presum[i+1]=presum[i]+nums[i];
       }
       int res=0;
       for(int left=0;left<len;left++){
           for(int right=left;right<len;right++){
               if(presum[right+1]-presum[left]==k){
                   res++;
               }
           }
       }
       return res;



    }
}

前缀和 + 哈希表优化

import java.util.HashMap;


class Solution {
    public int subarraySum(int[] nums, int k) {
    Map<Integer,Integer>map=new HashMap<>();
    map.put(0,1);
    int presum=0;
    int res=0;
    for(int i=0;i<nums.length;i++){
        presum+=nums[i];
        if(map.containsKey(presum-k)){
            res+=map.get(presum-k);
        }
        map.put(presum,map.getOrDefault(presum,0)+1);

    }
    return res;



    }
}