题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个整数数组和一个整数 k，要求其中所有子数组的数量，不过子数组需要满足一个条件，即其中的奇数的个数恰好为 k。

思路分享

  • 和【Leetcode Daily】930和相同的二元子数组类似的恰好型不定长滑动窗口，不过本题让陆爻齐更深入的思考，越长越合法的左指针的意义。

  • “众”所周知，我们灵神派的越长越合法类型的解法，是通过累计窗口左指针数值之和计算得出，其意义，除了充当窗口的左侧边界，实质意义可以理解为，窗口左侧满足条件的情况数目，而窗口本身是在遍历右指针情况，这样一来就算是统计了所有情况。

  • 拿第一次满足条件的窗口举例，此时，窗口的左侧还在起点，下标为 0，示意着此前没有满足条件的情况，进入中间的循环，循环的作用是找出不满足条件的边界；如果第一个元素（下标为 0 的那个）恰好是窗口需要的元素，那么左指针右移一步后，因窗口不符合条件而终止循环，此时左指针下标为 1，同时也寓意着以后的窗口都有这一个合法情况。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int left1 = 0, left2 = 0, goal1 = k, goal2 = k+1;
        int ans = 0, count1 = 0, count2 = 0;
        for (int right = 0; right < nums.size(); right++) {
            count1 += nums[right]&1;
            count2 += nums[right]&1;
            while(count1 >= goal1) {
                count1 -= nums[left1++]&1;
            }
            while(count2 >= goal2) {
                count2 -= nums[left2++]&1;
            }
            ans += left1-left2;
        }
        return ans;
    }
};