一、题目

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

说明 :

  1. 数组的长度为 [1, 20,000]。
  2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

点击查看原题
难度级别： 中等

二、思路

1）前缀和+HashMap

本题种k不一定为正数，那不能单纯从大于小于连续元素的和进行判断。
利用前缀和可以得到sum[0,j]，如果要求sum[i,j]，直接使用前缀和进行相减即可。那么要使j结尾的连续元素和为k，直接查找(0,j-1)中值为sum[0,j]-k的前缀和个数

三、代码

1）前缀和+HashMap

  1. class Solution {
  2.     public int subarraySum(int[] nums, int k) {
  3.         int ans = 0;
  4.         Map<Integer, Integer> map = new HashMap();
  5.         map.put(0, 1);    // 前缀和为0的数量初始化为1，即sum[0,i]-0=k，这种情况也计入答案内
  6.         for (int i = 0; i < nums.length; i++) {
  7.             if (i != 0) {
  8.                 nums[i] += nums[i-1];
  9.             }
  10.             ans += map.getOrDefault(nums[i] - k, 0);
  11.             map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);    // 保证前缀和只记录了（0，i-1）范围的
  12.         }
  13.         return ans;
  14.     }
  15. }
  1. 时间复杂度为`O(n)`，空间复杂度为`O(n)`