原文链接: https://leetcode-cn.com/problems/subarray-sum-equals-k

英文原文

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

 

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

 

Constraints:

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

中文题目

给你一个整数数组 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、暴力法（超时）

• 索引 i 和 j 确定一个子数组，枚举出所有子数组，子数组求和等于 k 的话则 count++。

• 遍历 i、 遍历 j、 从 i 到 j 的累加求和。 三重循环，时间复杂度$O(n^3)$

[]

const subarraySum = (nums, k) => {

  let count = 0;

  for (let i = 0; i < nums.length; i++) {

    for (let j = i; j < nums.length; j++) {

      let sum = 0;

      for (let q = i; q <= j; q++) {

        sum += nums[q];

      }

      if (sum == k) count++;

    }

  }

  return count;

};

[]

func subarraySum(nums []int, k int) int {

	count := 0

	for i := 0; i < len(nums); i++ {

		for j := i; j < len(nums); j++ {

			sum := 0

			for q := i; q <= j; q++ {

				sum += nums[q]

			}

			if sum == k {

				count++

			}

		}

	}

	return count

}

2、去除重复计算

• 求和时：上轮迭代求了 i 到 j - 1 的和，这轮就没必要从头求 i 到 j 的和。

• 去掉内层循环，用一个变量保存上次的求和结果，每次累加当前项即可。

• 依旧是穷举，时间复杂度：$O(n^2)$。还能再优化吗？

• Runtime: 900 ms, faster than 5.03% of Go online submissions

[]

const subarraySum = (nums, k) => {

  let count = 0;

  for (let i = 0; i < nums.length; i++) {

    let sum = 0;

    for (let j = i; j < nums.length; j++) {

      sum += nums[j];

      if (sum == k) count++;

    }

  }

  return count;

};

[]

func subarraySum(nums []int, k int) int {

	count := 0

	for i := 0; i < len(nums); i++ {

		sum := 0

		for j := i; j < len(nums); j++ {

			sum += nums[j]

			if sum == k {

				count++

			}

		}

	}

	return count

}

3、引入前缀和

• 前缀和：nums 的第 0 项到 当前项 的和。

• 定义 prefixSum 数组，prefixSum[x]：第 0 项到 第 x 项 的和。

$$prefixSum[x] = nums[0] + nums[1] +…+nums[x]$$

• nums 的某项 = 两个相邻前缀和的差：

$$nums[x] = prefixSum[x] - prefixSum[x - 1]$$

• nums 的 第 i 到 j 项 的和，有：

$$nums[i] +…+nums[j]=prefixSum[j] - prefixSum[i - 1]$$

• 当 i 为 0，此时 i-1 为 -1，我们故意让 prefixSum[-1] 为 0，使得通式在i=0时也成立：

$$nums[0] +…+nums[j]=prefixSum[j]$$

题目的等价转化

• 题意：有几种 i、j 的组合，使得从第 i 到 j 项的子数组和等于 k。

  ↓ ↓ ↓ 转化为 ↓ ↓ ↓

• 有几种 i、j 的组合，满足 $prefixSum[j] - prefixSum[i - 1] == k$。

• 可以通过求出 prefixSum 数组的每一项，再看哪些项相减等于k，求出count。

• 但该通式有 2 个变量，需要两层循环才能找出来，依旧是 $O(n^2)$。

不用求出 prefixSum 数组

• 其实我们不关心具体是哪两项的前缀和之差等于k，只关心等于 k 的前缀和之差出现的次数c，就知道了有c个子数组求和等于k。

• 遍历 nums 之前，我们让 -1 对应的前缀和为 0，这样通式在边界情况也成立。即在遍历之前，map 初始放入 0:1 键值对（前缀和为0出现1次了）。

• 遍历 nums 数组，求每一项的前缀和，统计对应的出现次数，以键值对存入 map。

• 边存边查看 map，如果 map 中存在 key 为「当前前缀和 - k」，说明这个之前出现的前缀和，满足「当前前缀和 - 该前缀和 == k」，它出现的次数，累加给 count。

代码

时间复杂度 O(n) 。空间复杂度 O(n)

[]

const subarraySum = (nums, k) => {

  const map = { 0: 1 };

  let prefixSum = 0;

  let count = 0;



  for (let i = 0; i < nums.length; i++) {

    prefixSum += nums[i];



    if (map[prefixSum - k]) {

      count += map[prefixSum - k];

    }



    if (map[prefixSum]) {

      map[prefixSum]++;

    } else {

      map[prefixSum] = 1;

    }

  }

  return count;

};

[]

func subarraySum(nums []int, k int) int {

	count := 0

	hash := map[int]int{0: 1}

	preSum := 0



	for i := 0; i < len(nums); i++ {

		preSum += nums[i]

		if hash[preSum-k] > 0 {

			count += hash[preSum-k]

		}

		hash[preSum]++

	}

	return count

}

复盘总结

• 每个元素对应一个“前缀和”

• 遍历数组，根据当前“前缀和”，在 map 中寻找「与之相减 == k」的历史前缀和

• 当前“前缀和”与历史前缀和，差分出一个子数组，该历史前缀和出现过 c 次，就表示当前项找到 c 个子数组求和等于 k。

• 遍历过程中，c 不断加给 count，最后返回 count

前前后后反复润色，应该蛮好懂了。欢迎提问评论建议，也欢迎关注我，我会继续产出题解。

统计信息

通过次数	提交次数	AC比率
164798	369547	44.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
两数之和	简单
连续的子数组和	中等
乘积小于K的子数组	中等
寻找数组的中心下标	简单
和可被 K 整除的子数组	中等