560. 和为K的子数组


阅读量123

题目

560. 和为 K 的子数组

https://leetcode-cn.com/problems/subarray-sum-equals-k/

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

示例 1 :

输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

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

题解

思路

两重循环遍历查询,但最后一个测试用例超时、

代码

/** * @param {number[]} nums * @param {number} k * @return {number} */ var subarraySum = function(nums, k) { const length = nums.length; let ans = 0; let sum; for(let i = 0; i < length; i++){ sum = 0; for(let j = i; j < length; j++){ sum += nums[j]; if(sum === k){ ans++; } } } return ans; };

官方

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; };

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; };

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 键值对。
  • 遍历 nums 数组,求每一项的前缀和,统计对应的出现次数,键值对方式存入 map。
  • 边存边查看 map,如果 map 中存在 key 为「当前前缀和 - k」,说明这个之前出现的前缀和,满足「当前前缀和 - 该前缀和 == k」,它出现的次数,累加给 count。

复盘总结

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

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

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

  • 遍历过程中,c 不断加给 count,最后返回 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; };

czbiao 2021年5月30日 21:19 收藏文档
本站总访问量10569
本站访客数9522人次