Leetcode | 第B节：数组综合题（2）
大家好啊！
抱歉这一节相对隔得时间长了一些再发出来，因为这几天基本上主要时间都在关注东京奥运会的比赛现场。在发表这篇文章的时候，也恰好知道名将苏炳添以9‘83’‘的时间晋级决赛，我认为他可以以这个成绩再拿一次金牌，希望我的预言成真2333
这一节我们会继续我们上一节的内容，介绍一些数组相关的问题。当然在这一节，我们主要会关注一些新方法的实践，包括前缀和，双指针，滑动窗口等。它们都是数组相关问题的解决手段和思路，相对来说也都是比较重要的技术和知识点。
那么我们开始吧。
数组综合题
前缀和
Problem 1: Leetcode 209 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
比方说输入是target = 7, nums = [2,3,1,2,4,3]，那么输出就是2，因为nums的结果中，[4, 3]是长度最小的子数组。
这个问题算是一个前缀和的典型问题。这么说的原因是，我们可以用前缀和这个工具来刻画这个问题的目标，并且想到一些容易的优化方法。
假设我们有一个数组
，那么前缀和的想法就是设
，这样的话，在
这个范围内的数组和，就可以用
来描述。
对于这个问题，一个想法是，既然我们要找到不同的区间和，那么自然就是要找到不同的
的组合。所以一个自然的想法就是，固定
，然后去枚举
，找到最合适的target对应的数组长度即可。
但是如果是单纯的枚举，这里的复杂度就是
，有没有更快的方法？当然有。注意到数组每一个元素都是正整数，所以我们在枚举
从小到大的过程中，
一定是会更大的。所以可以考虑在这里对
使用二分查找。这样的话，复杂度会变成
。这就好很多了。
关于二分查找，可以看看这一篇文章。这里就不多说了。
好的，我们来看看代码吧。
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
vector<int> sums(n + 1, 0);
// 为了方便计算，令 size = n + 1
// sums[0] = 0 意味着前 0 个元素的前缀和为 0
// sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
// 以此类推
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1]; // 前缀和
}
for (int i = 1; i <= n; i++) {
int target = s + sums[i - 1]; // 这里稍微做了一些变换。简单来说，不计算S_j - S_i来比较target，而是先修改target（对应代码中的s）为target + S_i，再比较它与S_j的大小。
auto bound = lower_bound(sums.begin(), sums.end(), target);
if (bound != sums.end()) {
ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1))); // 最终看数组长度为多少。
}
}
return ans == INT_MAX ? 0 : ans;
}
};
Problem 2: Leetcode 974 给定一个整数数组
A，返回其中元素之和可被K整除的（连续、非空）子数组的数目。
比方说输入A = [4,5,0,-2,-3,1], K = 5，那么输出就是7，因为一共有7个子数组满足要求。比方说这里的[5,0]就是满足要求的。
这依然是一道连续子数组的题目，所以我们也会考虑到使用前缀和的工具。事实上，这里我们希望看到的是
的倍数，而这在前缀和的意义上就是
和
同余（做带余除法可以得到相同的余数）。所以这个问题其实很简单，枚举一遍，去计算每一个位置对应的余数就可以了。
现在我们假如说在数组中，我们统计出了有
个位置，它们的余数相同，那么根据排列组合，可以发现一共可以产生
个搭配。比方说如果有3个位置的前缀和对应的余数相同（不妨假设是1, 2, 4）那么容易发现，
都是符合要求的子数组对应的和。
好的，那么我们来看看代码应该怎么写吧。
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> record = {{0, 1}}; // 设立一个哈希表，记录不同余数下对应的元素个数。
int sum = 0;
for (int elem: nums) {
sum += elem;
// 注意 C++ 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
int modulus = (sum % k + k) % k;
++record[modulus];
}
int ans = 0;
for (auto [x, cx]: record) {
ans += cx * (cx - 1) / 2;
}
return ans;
}
};
这里要多注意的是，余数的计算方式在不同的编程语言下会有不同的结果（有可能会有负数）。
这里还要注意的是，一开始初始化的时候，对于0这个余数，我们的初始化为1。这是因为如果一个前缀和的余数为0，这就说明了本身这个前缀和也是一个符合要求的子数组（起点就是数组的起点）。这么调整之后，读者可以自己验证，计算的结果一定是对的。
Problem 3: Leetcode 560 给定一个整数数组和一个整数 **k，**你需要找到该数组中和为 k 的连续的子数组的个数。
比方说输入是nums = [1,1,1], k = 2，那么输出就是2，这里要注意，子数组[1, 1]可能指的是前两个1，也有可能是后两个1，因此答案是2而不是1。
面对子数组的问题，前缀和是一个非常好的工具，事实上，对于这一个问题，我们的目的就是要找到所有符合条件的
，使得
。换句话说，
。也就是说，我们可以先枚举一遍
，把所有的可能的值存在一个哈希表中，再枚举
。
对于某一个
，如果可以在哈希表中找到一个对应的
，看似是一个好的结果。但是事实上，还有一个条件没有满足，就是
。所以有一个解决的方案就是，我们可以边更新哈希表，边进行统计。所以在这里，我们应该先计算
，然后看之前的结果中有没有对应的
出现，用哈希表来记录出现了几个。这样的话，如果出现，那么
一定是事先被计算过了。这个时候条件就可以满足了。
好的，我们来看看代码吧。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0, pre = 0;
for (auto& x:nums) {
pre += x;
if (mp.find(pre - k) != mp.end()) {
count += mp[pre - k];
}
mp[pre]++;
}
return count;
}
};
注意，这里的统计方式略微有些不同，是把公式变成了
来求解的。但是本质上是相同的。
Problem 4: Leetcode 525 给定一个二进制数组
nums, 找到含有相同数量的0和1的最长连续子数组，并返回该子数组的长度。
比方说如果输入是nums = [0,1,0]，那么输出就是2，因为[0, 1]或者[1, 0]都是符合条件的，但是[0, 1, 0]不是。
对于这个问题的话，首先可以做一个修改，就是，把所有的0都改成-1。为什么呢？因为这样的话，只要有相同的数量，那么连续子数组的和就是0，在统计上就会更加容易一些。其次，我们考虑，既然要求的是满足
的下标
，那么自然的，我们可以使用哈希表，来记录是否我们在遍历
的同时，
已经出现过。如果出现过，那么就说明找到了，那么既然我们需要找到“最长的”，那么记录一个前缀和对应的最早出现的位置肯定是必要的。因此其实这里我们不需要记录每一个前缀和出现过几次，而是记录它的位置即可。
因此算法其实是这样的：
- 如果某一个前缀和已经在哈希表中存在，那么根据当前的下标和哈希表中记录的“第一次出现的下标”，就可以得到我们的满足条件的数组长度，并且它是当前情况可以获得的最长的结果。
- 如果某一个前缀和还没存在，那么在哈希表中记录它，并且记录它出现的位置。
好的，我们来看看代码吧。
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int maxLength = 0;
unordered_map<int, int> mp;
int counter = 0;
mp[counter] = -1; // 一开始的位置前缀和是0，根据规定我们要记为-1
int n = nums.size();
for (int i = 0; i < n; i++) {
int num = nums[i];
if (num == 1) {
counter++; // 遇到一个1，相当于遇到一个1（听君一席话，胜听一席话）
} else {
counter--; // 遇到一个0，相当于遇到一个-1
}
if (mp.count(counter)) {
int prevIndex = mp[counter];
maxLength = max(maxLength, i - prevIndex);
} else {
mp[counter] = i;
}
}
return maxLength;
}
};
好的，关于前缀和的问题，我们就写到这里。
滑动窗口
滑动窗口相关的问题往往都是传统的模拟题，因此在思考难度上不会特别大。
Problem 5: Leetcode 1052 今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。 在某些时候，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。 书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。 请你返回这一天营业下来，最多有多少客户能够感到满意。
比方说输入是customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3，那么输出就是16。可以看出，实际的策略是，让老板最后的3分钟（这里X = 3）不生气，而之前的都不控制，都有生气，这样的话，第2，4分钟的顾客就会不满意，其他时间的都会满意，对应的顾客数就是1 + 1 + 1 + 1 + 7 + 5 = 16。
对于这个问题，其实使用滑动窗口非常好解决。首先，这个“连续X分钟不生气“肯定是要用完的，因为你不生气的时间越长，肯定能够满意的顾客越多。其次，我们要选择一个合适的X分钟的区间，而且这个区间是连续的。这就是滑动窗口了。我们要计算的就是，加上这个区间之后，顾客的满意数会不会有额外的增益。
在这之后，我们要考虑的是，究竟选择哪一个区间？首先一个区间肯定对应一个窗口，其次，我们可以发现，滑动窗口的优势在于，我们移动这个区间的时候，不需要重复计算这个区间内的所有元素，而只需要关注最左边和最右边的结果。比方说这一个题目中，假如说我们从前3分钟向后移动了一下（变成了第2-4分钟），那么我们其实只需要去掉第1分钟对应的顾客和多考虑第4分钟对应的顾客，其它的地方我们是不用管的。这样的话，每一个区间的结果可以从上一个区间得到，而不需要每一步都把整个窗口遍历一遍来求得我们感兴趣的结果。
好的，我们来看一下代码怎么写吧。
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
int total = 0;
int n = customers.size();
for (int i = 0; i < n; i++) {
if (grumpy[i] == 0) {
total += customers[i]; // 计算“不使用秘密技巧”下的答案。
}
}
int increase = 0;
for (int i = 0; i < minutes; i++) {
increase += customers[i] * grumpy[i]; // 计算“使用秘密技巧下”的答案
}
int maxIncrease = increase;
for (int i = minutes; i < n; i++) {
increase = increase - customers[i - minutes] * grumpy[i - minutes] + customers[i] * grumpy[i]; // 这一步就是修改，可以看出去掉了最左边的元素，多考虑了最右边的元素。
maxIncrease = max(maxIncrease, increase);
}
return total + maxIncrease;
}
};
Problem 6: Leetcode 1031 给出非负整数数组 A ，返回两个非重叠（连续）子数组中元素的最大和，子数组的长度分别为 L 和 M。（这里需要澄清的是，长为 L 的子数组可以出现在长为 M 的子数组之前或之后。） 从形式上看，返回最大的 V，而 V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并满足下列条件之一： 0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或 0 <= j < j + M - 1 < i < i + L - 1 < A.length.
比方说如果输入是A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2，那么输出就是20。在这里对应的两个子数组是[9]和[6, 5]。可以看出来，确实是两个不重叠的子数组。
这个问题还是一种找连续子数组的问题。这里规定了不重叠，所以可以想到，两个子数组一定存在一条明确的分界线。所以我们可以枚举这一条分界线，然后区分左和右。比方说可以规定[A[0], ..., A[i]]（左边部分）这个区间内可以找一个长度为L的数组，然后在剩下的区间内找一个长度为M的数组。当然你也可以反过来。可以看出，一共是有4种安排的可能的。
划分清楚之后，就可以分别在左边和右边去用滑动窗口的方式，枚举可能的连续子数组和了。
这里为了方便，我们用dp[i][0]来表示在左边部分取长度为L的子数组可以达到的最好结果，而dp[i][1]表示在左边部分取长度为M的子数组可以达到的最好结果。类似可以给出dp[i][2]和dp[i][3]。所以，我们可以分别计算出这四种安排对应的状态，然后两两组合就可以了。具体的细节我们放到代码中来讲
class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
//计算dp, 4个滑动窗口, 4种情况
vector<vector<int>> dp(A.size(), vector<int>(4, 0));
int presum = 0;
int maxsum;
for (int i = 0; i < L; ++i)
{
presum += A[i];
}
maxsum = presum;
dp[L - 1][0] = maxsum;
for (int i = L; i < A.size(); ++i)
{
presum -= A[i - L];
presum += A[i];
maxsum = max(maxsum, presum);
dp[i][0] = maxsum; // 通过滑动窗口的方式，不断更新状态。
}
presum = 0;
for (int i = 0; i < M; ++i)
{
presum += A[i];
}
maxsum = presum;
dp[M - 1][1] = maxsum;
for (int i = M; i < A.size(); ++i)
{
presum -= A[i - M];
presum += A[i];
maxsum = max(maxsum, presum);
dp[i][1] = maxsum;
}
presum = 0;
for (int i = A.size() - 1; i >= A.size() - L; --i)
{
presum += A[i];
}
maxsum = presum;
dp[A.size() - L][2] = maxsum;
for (int i = A.size() - L - 1; i >= 0; --i)
{
presum -= A[i + L];
presum += A[i];
maxsum = max(maxsum, presum);
dp[i][2] = maxsum;
}
presum = 0;
for (int i = A.size() - 1; i >= A.size() - M; --i)
{
presum += A[i];
}
maxsum = presum;
dp[A.size() - M][3] = maxsum;
for (int i = A.size() - M - 1; i >= 0; --i)
{
presum -= A[i + M];
presum += A[i];
maxsum = max(maxsum, presum);
dp[i][3] = maxsum;
}
//计算答案，这里有两种可能的组合，一个是左L右M，一个是左M右L
int res = 0;
//L在M左边
for (int i = L; i <= A.size() - M; ++i)
res = max(res, dp[i - 1][0] + dp[i][3]);
//M在L左边
for (int i = M; i <= A.size() - L; ++i)
res = max(res, dp[i - 1][1] + dp[i][2]);
return res;
}
};
可以看出，确实没有太多困难的地方。
Problem 7: Leetcode 658 给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。 整数 a 比整数 b 更接近 x 需要满足： |a - x| < |b - x| 或者 |a - x| == |b - x| 且 a < b
比方说在这里，如果arr = [1,2,3,4,5], k = 4, x = 3，那么输出就是[1, 2, 3, 4]。
因为这里的数组是按照升序排列好的，所以滑动窗口的方法就有了可乘之机。容易发现的是，这k个数本质上也一定是连续的，所以就是一个窗口。滑动窗口的本质就是我们通过对窗口的改变，可以利用到上一个窗口的信息，这样在修改的时候就会大大节省时间复杂度。
当然这一个题对于滑动窗口的处理方式和前面两个题都有些不同。这一题我们可以考虑的是，一开始让全数组作为一个窗口，然后分别比较最左边和最右边，哪一个距离这个目标值x是更近的。对于更近的元素，我们就保留，否则就删去。这样的话一直删到只剩k个，目标就算达成了。
这个方法固然是容易的，但是好像也不是特别有必要。这个方法的时间复杂度是
，但是其实没有啥必要。毕竟完全没有必要直接动用全数组的信息呀。所以一个好的思路是，我们找到一个枢纽点，然后向左向右拓展
个元素。因为这个枢纽点一定是包括在答案中的，所以我们可以保证的是，这
个元素一定包含了我们的答案，那么剩下的步骤就仅仅是按照之前提到的方法，不停的删除元素，到只剩下
个即可了。
那么这个“枢纽点”是什么呢？其实就是第一个比这个目标元素
大的，或者小的元素。而这个其实是可以通过二分查找来完成的。因此本质上，这样的问题求解就是，先找到这个枢纽点，向左右拓展，再按照之前的方式删除元素。这样的时间复杂度是
。
那么我们来看看代码吧。
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int n = arr.size();
int l = 0, r = n-1;
while (l < r) {
int m = (l + r) / 2;
if (arr[m] < x) l = m + 1;
else r = m;
}
r = min(n-1, l+k-1);
l = max(0, l-k);
while (r-l >= k) {
if (x-arr[l] <= arr[r]-x) r--;
else l++;
}
vector<int> res(k);
copy(arr.begin()+l, arr.begin()+l+k, res.begin());
return res;
}
};
当然了其实这一个问题可以直接采用二分的思路来完成，虽然和本节主题无关，但我们也把这个思路提供给大家。注意到，在这个问题中，如果窗口的左边界需要被删除，说明窗口左边界的左边的所有元素都不可能是答案。因此事实上，可以直接划分一个长度为
的数组（位置为
），然后观察到底应该删除哪一边，而这个位置就可以通过二分的方法来进行枚举。
我们也来看看代码吧。
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int n = arr.size();
int l = 0, r = n-k;
while (l < r) {
int m = (l + r) / 2;
if (x-arr[m] > arr[m+k]-x) l = m + 1;
else r = m;
}
vector<int> res(k);
copy(arr.begin()+l, arr.begin()+l+k, res.begin());
return res;
}
};
读者可以自己思考一下，为什么我们取了一个长度为
的数组，而不是
。
双指针
对于Problem 7，其实很多人也会把它归类到双指针这一类的问题中。当然双指针相关的问题也是很丰富的，这里我们也摘录几道。
Problem 8: Leetcode 15 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。
比方说输入nums = [-1,0,1,2,-1,-4]，那么输出是[[-1,-1,2],[-1,0,1]]。可以看出，确实这个三元组内的和为0，并且一共有2种可能。
这一个题是非常经典的3Sum问题，它的地位类似于大家一开始就开始刷的Two Sum，类似于英文单词的abandon一样，永远是第一个映入眼帘的题目……
对于这个问题，一个很容易考虑到的方法是使用三重循环。同时为了防止重复，我们要先对数组做一个排序，排序之后，内层循环找到的元素一定不小于外层循环的，因此只需要再额外判断每一次的单循环中，下次找到的元素是否和上一次找到的不一样（比方说数组有可能有几个连续的相同的元素，那么即使排序过了，在循环的时候也依然会出现重复），即可完全排除重复的情况。注意这里的重复是说，同样的一个三元组不能多次放到答案中，而不是说一个三元组内的三个元素都必须互不相同。
到此为止，我们还是三重循环，我们也并没有提到“双指针”这个概念。事实上，一个关键的点是，当我们选择好了
之后，
就是固定的。因此排序之后，如果我们把
的循环指针向右移，那就会遇到一个不小于它的新的元素
。那么对应的新的
一定满足
，换句话说，可以把
的指针向左移动，而不是再来一次循环。这个制约决定了，其实这个问题完全没有三重循环的必要，最后的两重循环完全可以并在一起，用两个指针来枚举完成，这也就是双指针的含义。
因为减掉了一个循环，所以三重循环变成了二重循环，这样就好多了。
那么我们来看看代码吧。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧，否则会产生重复
while (second < third && nums[second] + nums[third] > target) {
--third; // 这就是双指针
}
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
Problem 9: Leetcode 992 给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。 （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。） 返回 A 中好子数组的数目。
对于这个问题，一个好的方式当然是，遍历所有的区间，然后统计区间内不同元素的个数。但是很明显这样的话时间复杂度很高，所以应该有些优化的方法。
注意到如果我们已经给定了一个区间
，那么在右移动
的时候，对应的左边的
一定要向右移动，而且事实上，
不一定是一个确定的数，而是一个范围。因为事实上，完全有可能同一个
对应的
不止一个。因此综合一下就是，一开始我们用两个指针
，从头开始枚举确认一个初始区间
。然后先向右移动
，每一次移动
的时候，都确定一个
的范围
，那么就可以得到，子区间的数目就是
。而且可以保证的是，向右移动
的时候，
是不需要向左移动的，因此可以看出，最终两个指针都会遍历完整个数组，从最左移动到最右。对应的时间复杂度是
。
好的，那我们来看看代码吧。
class Solution {
public:
int subarraysWithKDistinct(vector<int>& A, int K) {
int n = A.size();
int cl[n+1], cr[n+1], l = 0, r = 0; // 分别用cl，cr当作哈希，来记录每一个元素出现的次数，进而统计不同元素的个数
int res = 0, nl = 0, nr = 0;
memset(cl, 0, sizeof cl);
memset(cr, 0, sizeof cr);
for (int i = 0; i < n; ++i) {
if (cl[A[i]]++ == 0) nl++;
while (nl > K) {
if (--cl[A[l++]] == 0) nl--;
}
if (cr[A[i]]++ == 0) nr++;
while (nr >= K) {
if (--cr[A[r++]] == 0) nr--;
}
res += r - l;
}
return res;
}
};
Problem 10: Leetcode 1248 给你一个整数数组 nums 和一个整数 k。 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。 请返回这个数组中「优美子数组」的数目。
这一个问题也可以使用双指针，不过做法也是有一点技巧的。首先我们为了方便，就直接把奇数设置为1，偶数设置为0。
那么一个容易发现的结论是，如果我们考虑设置了一个区间，且它的左右边界都是1，并且包括边界，区间内一共涵盖了
个1，那么这个边界如果左边有
个0，右边有
个0，根据排列组合可以看出，一共会有
个区间，涵盖了
个1。因此我们可以通过记录每一个
的位置来判断位置。
有没有更好的结果呢？当然也是有的，我们可以通过双指针的方式，节省一些空间复杂度。简单来说，even 记录子数组前面有多少个 0 ，cnt 记录当前子数组有多少个 1 。用 l 指向子数组开头，r 指向子数组结尾。
如果 cnt = k ，那就说明子数组中正好有 k 个 1 。那就右移 l ，直到遇到 1 为止，这样就能统计出左边有多少个 0，记录在 even 中。然后 l 右移跳过这个 1 ，同时 cnt 减一。
如果 cnt < k ，那就说明 1 的数量不够，r 继续右移就行了。同时每移动一次，答案都要加上 even 值，因为你之前 cnt = k 时记录了一下左边 0 的数量，现在右边每一个 0 都得加上它。
因为这里我们讲的是双指针，所以我们给出双指针的代码。
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size();
int res = 0, cnt = 0, even = 0;
int l = 0, r = 0;
while (r < n) {
if (cnt < k && (nums[r++]&1)) cnt++; // 这里是一个位运算，用于判断奇偶性
if (cnt == k) {
even = 1;
while (!(nums[l++]&1)) even++;
cnt--;
}
res += even;
}
return res;
}
};
Problem 11: Leetcode 71 给定一个正整数数组
nums和整数k。 请找出该数组内乘积小于k的连续的子数组的个数。
这一个问题的解决思路和前面基本相同，这里我们仅仅拿出来做一个巩固练习。简单来说，我们维护两个指针，然后移动右边的指针。这是因为固定左边指针的时候，右边指针越往右移动，乘积就会越大，所以我们可以一直往右移动，然后到乘积
的时候，再移动左边的指针。具体的细节我们直接放代码，因为之前分析的足够多了，我们就不多赘述了。
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
int prod = 1, ans = 0, left = 0;
for (int right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
ans += right - left + 1;
}
return ans;
}
}
当然了，这是一串Java代码。
小结
这一节我们继续介绍了一些数组相关的问题，但更主要是关注了数组类型题目的三个方法：前缀和，滑动窗口和双指针。相关的题目多和数学和“连续子数组”这个条件相关。
在下一节，我们会开始介绍一些字符串相关的问题。我们的形式会和数组类似，先介绍一些综合题，再看是否可以有一些专门的方法类型的题目可以被我们归纳出来。
腾讯云开发者
