560. 和为 K 的子数组

type

status

date

slug

summary

category

icon

password

创建时间

Nov 15, 2024 12:51 AM

小米 - 2024/11/12 和为 k 的子数组的个数

示例 1: 输入: [2, 3, 3, 1], k = 6 输出: 1 解释: 只有子数组 [3, 3] 的和为 6

示例 2: 输入: [2, 3, 1, 5], k = 6 输出: 2 解释: 子数组 [2, 3, 1] 和子数组 [1, 5] 的和为 6

思路一：首先的想法是滑动窗口，操作就是“水多加面，面多加水”。具体思路是如果当前数组的和小于目标值 k ，就右移右指针，让新的值进入；否则，就右移左指针，让旧的值出去。

上面的想法是好的，但是忽略了负数。当数组有负数，上面判断指针移动的条件就没办法了。──滑动窗口需要满足单调性

改进思路后，超时了 😅😅😅

思路二：

在上述改进思路后，我们发现存在较多的重复求和运算。想到了利用前缀和，来加速。

勉强通过，问题出现在两层循环那里。

sum = k = s[r + 1] - s[l] 变形得 k = s[r + 1]+ (-s[l]) 。我们发现题目很像两数之和。s[l]= s[r + 1] - k ，根据当前值，找过去是否存在满足条件的值。

一次遍历优化，这里参考灵茶山艾府

补充知识──前缀和模板题

303. 区域和检索 - 数组不可变

给定一个整数数组 nums，处理以下类型的多个查询:

实现 NumArray 类：

int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

C++

Java

总结：前缀和的一般模板

📎 参考