10 前缀和+哈希：和为K的子数组 560

目录

• 浅浅试一下
  
• 区域和检索-数组不可变 303
  
• 再做最初的那道题
  
• 变形题
  
• 长度最小的子数组 209
  

浅浅试一下

我的思考：大眼一看，这道题应该是 不定长滑动窗口。
那我只要先从头找到一个最接近k或者等于k的leftsum，然后慢慢向右滑动即可。
OK，开始写代码
一个小时过去了，
没写出来。
唉，看题解吧。
区域和检索-数组不可变 303

一个长度为n的数组，有多少个子数组呢？
对于任意一个子数组

• 子数组的起点有n个选择。
  
• 子数组的终点有n-起点个选择
  如长度为3的数组[1, 2, 3]
  
• 子数组起点有3个选择
  
• 起点为0的子数组终点也有\(3-0=3\)个选择
  

综上，一个数组的子数组数量级是\(O(n^{2})\)
同样地，一个数组的前缀和是\(O(n)\)
任意子数组的和都可以表示为两个前缀和的差值。
再做最初的那道题

点击查看代码

1. class Solution {
2. public:
3.     int subarraySum(vector<int>& nums, int k) {
4.         int ans = 0;
5.         //计算前缀和
6.         vector<int> vec(nums.size() + 1);
7.         vec[0] = 0;
8.         for (int i = 0; i < nums.size(); ++i) {
9.             vec[i+1] = vec[i] + nums[i];
10.         }
11.         unordered_map<int, int> m;
12.         for (auto& val: vec) {
13.             if (m.contains(val - k))
14.                 ans += m[val - k];
15.             ++m[val];
16.         }
17.         return ans;
18.     }
19. };

复制代码

其实这个代码，我不是很能理解。
思路是这样的：

• 先计算前缀和
  
• 然后因为每个子数组都可以表示成两个前缀和的差值，所以只需要遍历前缀和数组，看哈希表中是否有相应的值即可。
  

注：vec[0]表示第0个元素前缀和为0
时间复杂度：O(n)
空间复杂度：O(n)
问：为什么这题不适合用滑动窗口做？
答：滑动窗口需要满足单调性，当右端点元素进入窗口时，窗口元素和是不能减少的。本题 nums 包含负数，当负数进入窗口时，窗口左端点反而要向左移动，导致算法复杂度不是线性的。
额，这道题好难理解，头大。
变形题

• 
  
  • 改成计算元素和等于 k 的最短子数组，要怎么做？
    
  
  
• 
  
  • 改成计算元素和等于 k 的最长子数组，要怎么做？
    
  
  
• 
  
  • 改成计算元素和等于 k 的所有子数组的长度之和，要怎么做？
    
  
  
• 
  
  • 改成元素和至多为 k，要怎么做？见 363. 矩形区域不超过 K 的最大数值和。
    
  
  
• 变形题1
  
• 变形题2
  
• 变形题3
  
• 变形题4
  

今天就到这里吧，学废了。
变形题想不明白，标记一下吧。
2025-05-27 10:06:49 星期二
书接上回，咱们再接再厉！
长度最小的子数组 209

点击查看代码

1. class Solution {
2. public:
3.     int minSubArrayLen(int target, vector<int>& nums) {
4.         //不定长滑动窗口
5.         int leftSum = 0;
6.         int left = 0;
7.         int minLen = INT_MAX;
8.         for (int i = 0; i < nums.size(); ++i) {
9.             leftSum += nums[i];
10.             if (leftSum < target)
11.                 continue;
12.             while (leftSum >= target) {
13.                 minLen = min(minLen, i - left + 1);
14.                 leftSum -= nums[left];
15.                 ++left;
16.             }
17.         }
18.         if (minLen == INT_MAX)
19.             return 0;
20.         return minLen;
21.     }
22. };

复制代码

受到昨天前缀和+哈希的影响，我感觉这道题也是这个套路，然后写了写没什么思路。
我不知道二次遍历那块应该咋修改，遂放弃。
然后我一看这个数组都是正数，复合滑动窗口的单调性，所以双指针滑动，就做出来了。
时间复杂度：O(n)
空间复杂度：O(1)
听灵神这道题的讲解。
首先考虑暴力做法，找出所有的子数组。
依次枚举每个左端点，向右扩展n + (n-1) + (n-2) +... + 1，\(O(n^{2})\)
优化成O(n)，参考我的做法。
还可以继续优化成\(O(\log n)\)
有时间再做吧。
713 乘积小于K的子数组
点击查看代码

1. class Solution {
2. public:
3.     int numSubarrayProductLessThanK(vector<int>& nums, int k) {
4.         int tmp = 1;
5.         int ans = 0;
6.         int left = 0, right = 0;
7.         for (int right = 0; right < nums.size(); ++right) {
8.             tmp *= nums[right]; //l r
9.             //[l r] [l+1 r] [r r]
10.             while (left <= right && tmp >= k) {
11.                 tmp = tmp / nums[left];
12.                 ++left;
13.             }
14.             if (tmp < k)
15.                 ans = ans + right - left + 1;
16.           }
17.         return ans;   
18.     }
19. };

复制代码

天哪，吐了！
虽然根上一题是一样的套路，但是总感觉哪里不太一样。
呼，今天就到这里吧。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！