子串

560. 和为K的子数组

//看了答案思路写的
class Solution {
    public int subarraySum(int[] nums, int k) {
        int sum[] = new int[nums.length+1];
        sum[0]=0;
        int count=0;
        //统计前面出现的次数 
        for(int i=1;i<sum.length;i++){
            sum[i] = sum[i-1]+nums[i-1];
            
        }
        //遍历数组，求出每个元素和为k的子数组的个数 
        for(int end=1;end<sum.length;end++){
            for(int start=1;start<=end;start++){
                if(sum[end]-sum[start-1]==k) count++;
            }
            
        }
        return count;

    }
}

//官方解
//使用了两数之和的做法 
public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap < Integer, Integer > mp = new HashMap < > ();
        mp.put(0, 1);
        //统计前面出现的次数 
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1); //统计前面出现的次数 
        }
        return count;
    }
}