Skip to main content

560. Subarray Sum Equals K

分析

题解

朴素求和版本

function subarraySum(nums: number[], k: number): number {
let ans = 0

for (let i = 0; i < nums.length; i++) {
let prevSum = 0
for (let j = i; j < nums.length; j++) {
prevSum = nums[j] + prevSum
if (prevSum === k) {
ans++
}
}
}

return ans
};

前缀和

function subarraySum(nums: number[], k: number): number {
let ans = 0
// 从 idx 0 开始形成的前缀和
// 和: 个数
const preSum: Record<number, number> = {}
preSum[0] = 1

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

const need = temp - k
if (preSum[need]) {
ans += preSum[need]
}
if (preSum[temp]) {
preSum[temp]++
} else {
preSum[temp] = 1
}
}

return ans
};