一、题目描述
给你一个整数数组 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
二、思路讲解
1、暴力
算出每一个连续子数组的和即可，超时。
public class Solution { public int subarraySum(int[] nums, int k) { int count = 0; for (int i=0; i<nums.length; i++) { int sum = 0; for (int j=i; j<nums.length; j++) { sum += nums[j]; if (sum == k) { count++; } } } return count; } }
时间复杂度： O(N^2)
空间复杂度： O(N)
2、保存前n个的和
暴力方法超时的原因是我们重复算了很多遍和，是否可以将这些和提前保存下来呢？
于是想到，我们使用数组sum[]，sum[i]表示数组中前i个数字的和（注意是前i个，而不是索引i之前），我们想要计算某一段子数组的和，比如索引i到j的和，只需计算sum[j+1] - sum[i]即可。
class Solution { public int subarraySum(int[] nums, int k) { int len = nums.length; // int sum = 0; int count = 0; int []sum = new int[len+1]; sum[1] = nums[0]; for(int i=2; i<len+1; i++) { sum[i] = sum[i-1] + nums[i-1]; } int left = 0; int right = 0; for(int i=0; i<len+1; i++) { for(int j=i+1; j<len+1; j++) { if((sum[j]-sum[i])==k) { count++; } } } return count; } }
时间复杂度： O(N^2)
空间复杂度： O(N)
3、哈希表优化
其实，当我们构建好sum数组后，问题转化为了：在sum数组中有几对差为k的数字？不难想到力扣中的第一道题：1. 两数之和-力扣 中使用哈希表优化时间的方式：我们将sum[i]的出现次数保存在哈希表中，然后去寻找sum[i] - k有几个，即可以O(1)的时间复杂度找到。
class Solution { public int subarraySum(int[] nums, int k) { int len = nums.length; int count = 0; int []sum = new int[len+1]; sum[1] = nums[0]; for(int i=2; i<len+1; i++) { sum[i] = sum[i-1] + nums[i-1]; } Map<Integer, Integer> map = new HashMap<>(); for(int i=0; i<len+1; i++) { if(map.containsKey(sum[i]-k)) { count += map.get(sum[i]-k); } map.put(sum[i], map.getOrDefault(sum[i], 0)+1); } return count; } }
时间复杂度： O(N)
空间复杂度： O(N)
