10 前缀和+哈希：和为K的子数组 560
目录[*]浅浅试一下
[*]区域和检索-数组不可变 303
[*]再做最初的那道题
[*]变形题
[*]长度最小的子数组 209
浅浅试一下
我的思考：大眼一看，这道题应该是 不定长滑动窗口。
那我只要先从头找到一个最接近k或者等于k的leftsum，然后慢慢向右滑动即可。
OK，开始写代码
一个小时过去了，
没写出来。
唉，看题解吧。
区域和检索-数组不可变 303
一个长度为n的数组，有多少个子数组呢？
对于任意一个子数组
[*]子数组的起点有n个选择。
[*]子数组的终点有n-起点个选择
如长度为3的数组
[*]子数组起点有3个选择
[*]起点为0的子数组终点也有\(3-0=3\)个选择
综上，一个数组的子数组数量级是\(O(n^{2})\)
同样地，一个数组的前缀和是\(O(n)\)
任意子数组的和都可以表示为两个前缀和的差值。
再做最初的那道题
点击查看代码class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0;
//计算前缀和
vector<int> vec(nums.size() + 1);
vec = 0;
for (int i = 0; i < nums.size(); ++i) {
vec = vec + nums;
}
unordered_map<int, int> m;
for (auto& val: vec) {
if (m.contains(val - k))
ans += m;
++m;
}
return ans;
}
};其实这个代码，我不是很能理解。
思路是这样的：
[*]先计算前缀和
[*]然后因为每个子数组都可以表示成两个前缀和的差值，所以只需要遍历前缀和数组，看哈希表中是否有相应的值即可。
注：vec表示第0个元素前缀和为0
时间复杂度：O(n)
空间复杂度：O(n)
问：为什么这题不适合用滑动窗口做？
答：滑动窗口需要满足单调性，当右端点元素进入窗口时，窗口元素和是不能减少的。本题 nums 包含负数，当负数进入窗口时，窗口左端点反而要向左移动，导致算法复杂度不是线性的。
额，这道题好难理解，头大。
变形题
[*]
[*]改成计算元素和等于 k 的最短子数组，要怎么做？
[*]
[*]改成计算元素和等于 k 的最长子数组，要怎么做？
[*]
[*]改成计算元素和等于 k 的所有子数组的长度之和，要怎么做？
[*]
[*]改成元素和至多为 k，要怎么做？见 363. 矩形区域不超过 K 的最大数值和。
[*] 变形题1
[*] 变形题2
[*] 变形题3
[*] 变形题4
今天就到这里吧，学废了。
变形题想不明白，标记一下吧。
2025-05-27 10:06:49 星期二
书接上回，咱们再接再厉！
长度最小的子数组 209
点击查看代码class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
//不定长滑动窗口
int leftSum = 0;
int left = 0;
int minLen = INT_MAX;
for (int i = 0; i < nums.size(); ++i) {
leftSum += nums;
if (leftSum < target)
continue;
while (leftSum >= target) {
minLen = min(minLen, i - left + 1);
leftSum -= nums;
++left;
}
}
if (minLen == INT_MAX)
return 0;
return minLen;
}
};受到昨天前缀和+哈希的影响，我感觉这道题也是这个套路，然后写了写没什么思路。
我不知道二次遍历那块应该咋修改，遂放弃。
然后我一看这个数组都是正数，复合滑动窗口的单调性，所以双指针滑动，就做出来了。
时间复杂度：O(n)
空间复杂度：O(1)
听灵神这道题的讲解。
首先考虑暴力做法，找出所有的子数组。
依次枚举每个左端点，向右扩展n + (n-1) + (n-2) +... + 1，\(O(n^{2})\)
优化成O(n)，参考我的做法。
还可以继续优化成\(O(\log n)\)
有时间再做吧。
713 乘积小于K的子数组
点击查看代码class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int tmp = 1;
int ans = 0;
int left = 0, right = 0;
for (int right = 0; right < nums.size(); ++right) {
tmp *= nums; //l r
//
while (left <= right && tmp >= k) {
tmp = tmp / nums;
++left;
}
if (tmp < k)
ans = ans + right - left + 1;
}
return ans;
}
};天哪，吐了！
虽然根上一题是一样的套路，但是总感觉哪里不太一样。
呼，今天就到这里吧。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]