和为K的子数组-560 #110

sl1673495 · 2020-06-29T13:28:52Z

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

示例 1 :

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

直接求解

不断的尝试从 0 ~ nums.length 确定一个左边界，然后分别尝试右边界 left + 1 ~ nums.length - 1，在确定左边界后这个遍历右边界的的过程中记录一个值 total，不断的增加它的值，一旦这个值和 k 相等，就把结果 res 的值加一。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
let subarraySum = function (nums, k) {
  let n = nums.length
  if (!n) {
    return 0
  }

  let res = 0
  for (let i = 0; i < n; i++) {
    let total = 0
    for (let j = i; j < n; j++) {
      total += nums[j]
      if (total === k) {
        res += 1
      }
    }
  }
  return res
}

前缀和

先提前构造好 sums 数组，sums[i] 代表数组长度为 i 的时候的和，这样求解 nums[left ~ right] 的值只需要求 sums[right + 1] - sums[left] 即可。其余的思路和上面的解法一样，由于上面的解法中也是用 total 变量不断累加而不是每次求和，所以这两种方法性能差距不大。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
let subarraySum = function (nums, k) {
  let n = nums.length
  if (!n) {
    return 0
  }

  let sums = []
  sums[0] = 0
  for (let i = 1; i <= n; i++) {
    sums[i] = sums[i - 1] + nums[i - 1]
  }

  let res = 0
  for (let left = 0; left < n; left++) {
    for (let right = left; right < n; right++) {
      let sum = sums[right + 1] - sums[left]
      if (sum === k) {
        res += 1
      }
    }
  }
  return res
}

sl1673495 added the 前缀和 label Jun 29, 2020

Oct	NOV	Dec
	29
2019	2020	2021

sl1673495 / leetcode-javascript

和为K的子数组-560 #110

和为K的子数组-560 #110

sl1673495 commented Jun 29, 2020 •

edited

sl1673495 / leetcode-javascript

Join GitHub today

GitHub is where the world builds software

和为K的子数组-560 #110

和为K的子数组-560 #110

Comments

sl1673495 commented Jun 29, 2020 • edited

思路

直接求解

前缀和

Essential cookies

Always active

Analytics cookies

sl1673495 commented Jun 29, 2020 •

edited