您现在的位置是:首页 > 正文

LeetCode 1248. Count Number of Nice Subarrays【前缀和,哈希表;数学;滑动窗口】中等

2024-02-01 04:33:14阅读 1

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。

请返回这个数组中 「优美子数组」 的数目。

示例 1:

输入:nums = [1,1,2,1,1], k = 3
输出:2
解释:包含 3 个奇数的子数组是 [1,1,2,1][1,2,1,1]

示例 2:

输入:nums = [2,4,6], k = 1
输出:0
解释:数列中不包含任何奇数,所以不存在优美子数组。

示例 3:

输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出:16

提示:

  • 1 <= nums.length <= 50000
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= nums.length

解法1 数学

这个题目中偶数其实是没有用的,可以单独建立一个 o d d odd odd 数组来记录第 i i i 个奇数的下标。那么枚举奇数,假设当前枚举到第 i i i 个,那么 [ o d d [ i ] , o d d [ i + k − 1 ] ] [odd[i],odd[i+k−1]] [odd[i],odd[i+k1]] 这个子数组就恰好包含 k k k 个奇数。由于奇数和奇数间存在偶数,所以一定存在其他子数组 [ l , r ] [l,r] [l,r] 、满足 [ l , r ] [l,r] [l,r] 包含 [ o d d [ i ] , o d d [ i + k − 1 ] ] [odd[i],odd[i+k−1]] [odd[i],odd[i+k1]] [ l , r ] [l,r] [l,r] 里的奇数个数为 k k k,那么这个需要怎么统计呢?

由于已经记录了每个奇数的下标,所以知道对于第 i i i 个奇数,它的前一个奇数的下标为 o d d [ i − 1 ] odd[i−1] odd[i1] ,也就是说 ( o d d [ i − 1 ] , o d d [ i ] ) (odd[i−1],odd[i]) (odd[i1],odd[i]) 间的数都为偶数。同理可得 ( o d d [ i + k − 1 ] , o d d [ i + k ] ) (odd[i+k−1],odd[i+k]) (odd[i+k1],odd[i+k]) 间的数也都为偶数。那么可以得出——满足 l ∈ ( o d d [ i − 1 ] , o d d [ i ]   ] l∈(odd[i−1],odd[i]\ ] l(odd[i1],odd[i] ] r ∈ [ o d d [ i + k − 1 ] , o d d [ i + k ] ) r∈[odd[i+k−1],odd[i+k]) r[odd[i+k1],odd[i+k]) 条件的子数组 [ l , r ] [l,r] [l,r] ,包含 [ o d d [ i ] , o d d [ i + k − 1 ] ] [odd[i],odd[i+k−1]] [odd[i],odd[i+k1]] [ l , r ] [l,r] [l,r] 里的奇数个数为 k k k 个。因此对于第 i i i 个奇数,它对答案的贡献为符合条件的 [ l , r ] [l,r] [l,r] 的个数,即:
( o d d [ i ] − o d d [ i − 1 ] ) × ( o d d [ i + k ] − o d d [ i + k − 1 ] ) (odd[i]−odd[i−1])×(odd[i+k]−odd[i+k−1]) (odd[i]odd[i1])×(odd[i+k]odd[i+k1])
只要遍历一遍 o d d odd odd 数组即可求得最后的答案,注意边界的处理。

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        int odd[n + 2], cnt = 0;
        for (int i = 0; i < n; ++i)
            if (nums[i] & 1) odd[++cnt] = i; // 记录第cnt个奇数的下标
        odd[0] = -1, odd[++cnt] = n; // 两个哨兵
        for (int i = 1; i + k <= cnt; ++i) // cnt已经加了1
            ans += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1]);
        return ans;
    }
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 为数组的大小。遍历 o d d odd odd 数组最坏情况下需要 O ( n ) O(n) O(n) 的时间。
  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 为数组的大小。 o d d odd odd 数组需要 O ( n ) O(n) O(n) 的空间。

解法2 前缀和+哈希表

考虑以 i i i 结尾的「优美子数组」个数,我们需要统计符合条件的下标 j j j 的个数,其中 0 ≤ j ≤ i 0≤j≤i 0ji 这个子数组里的奇数个数恰好为 k k k 。如果枚举 [ 0.. i ] [0..i] [0..i] 里所有的下标来判断是否符合条件,那么复杂度将会达到 O ( n 2 ) O(n^2) O(n2) ,无法通过所有测试用例,因此需要优化枚举的时间复杂度

我们定义 s u m [ i + 1 ] sum[i+1] sum[i+1] [ 0.. i ] [0..i] [0..i] 中奇数的个数,则 s u m [ i + 1 ] sum[i+1] sum[i+1] 可以由 s u m [ i ] sum[i] sum[i] n u m s [ i ] nums[i] nums[i] 递推而来,即:
s u m [ i + 1 ] = s u m [ i ] + ( n u m s [ i ] & 1 ) sum[i+1]=sum[i]+(nums[i]\& 1) sum[i+1]=sum[i]+(nums[i]&1)
那么「 [ j . . . i ] [j...i] [j...i] 这个子数组里的奇数个数恰好为 k k k 」这个条件可转化为
s u m [ i + 1 ] − s u m [ j ] = = k sum[i+1]−sum[j]==k sum[i+1]sum[j]==k
简单移项,可得符合条件的下标 j j j 需要满足
s u m [ j ] = = s u m [ i + 1 ] − k sum[j]==sum[i+1]−k sum[j]==sum[i+1]k
所以,考虑以 i i i 结尾的「优美子数组」个数时,只要统计有多少个奇数个数为 s u m [ i + 1 ] − k sum[i+1]−k sum[i+1]k 即可。我们只要建立频次数组/哈希表 c n t cnt cnt 记录 s u m [ i ] sum[i] sum[i] 出现的次数,从左往右边更新 c n t cnt cnt 边计算答案,那么以 i i i 结尾的答案 c n t [ s u m [ i ] − k ] cnt[sum[i]−k] cnt[sum[i]k] 即可 O ( 1 ) O(1) O(1) 得到。最后的答案即为所有下标结尾的「优美子数组」个数之和。

需要注意的是,从左往右边更新边计算时,已经保证了 c n t [ s u m [ i + 1 ] − k ] cnt[sum[i+1]−k] cnt[sum[i+1]k] 里记录的 s u m [ j ] sum[j] sum[j] 的下标范围是 0 ≤ j ≤ i 0≤j≤i 0ji 。同时,由于 s u m [ i ] sum[i] sum[i] 的计算只与前一项的答案有关,因此可以不用建立 s u m sum sum 数组,直接用 s u m sum sum 变量来记录即可。

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size(), sum = 0, ans = 0;
        // unordered_map<int, int> cnt;
        int cnt[n + 1];
        memset(cnt, 0, sizeof(cnt));
        cnt[0] = 1;
        for (int i = 0; i < n; ++i) {
            sum += (nums[i] & 1);
            ans += sum >= k ? cnt[sum - k] : 0;
            ++cnt[sum];
        }
        return ans;
    }
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 为数组的大小。只需遍历一遍数组即可求得答案。
  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 为数组的大小。频次数组 c n t cnt cnt 记录的最大值不会超过 n n n ,因此只需要额外的 O ( n ) O(n) O(n) 的空间。

解法3 快慢指针+滑动窗口

这个解法是解法1的空间优化版。我们不断右移 r i g h t right right 指针来扩大滑动窗口,使其包含 k k k 个奇数;若当前滑动窗口包含了 k k k 个奇数,则如下「计算当前窗口的优美子数组个数」:

  1. 统计第 1 1 1 个奇数左边的偶数个数 l e f t E v e n C n t leftEvenCnt leftEvenCnt 。 这 l e f t E v e n C n t leftEvenCnt leftEvenCnt 个偶数都可以作为「优美子数组」的起点,因此起点的选择有 l e f t E v e n C n t + 1 leftEvenCnt + 1 leftEvenCnt+1 种(因为可以一个偶数都不取)。
  2. 统计第 k k k 个奇数右边的偶数个数 r i g h t E v e n C n t rightEvenCnt rightEvenCnt 。 这 r i g h t E v e n C n t rightEvenCnt rightEvenCnt 个偶数都可以作为「优美子数组」的终点,因此终点的选择有 r i g h t E v e n C n t + 1 rightEvenCnt + 1 rightEvenCnt+1 种(因为可以一个偶数都不取)。
  3. 因此「优美子数组」左右起点的选择组合数为 ( l e f t E v e n C n t + 1 ) × ( r i g h t E v e n C n t + 1 ) (leftEvenCnt + 1) \times (rightEvenCnt + 1) (leftEvenCnt+1)×(rightEvenCnt+1)
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        int left = 0, right = 0, oddCnt = 0;
        while (right < n) {
            // 右指针先走,每遇到一个奇数则+1
            if (nums[right++] & 1) ++oddCnt;
            // 若当前滑动窗口[left,right)有k个奇数,进入此分支统计当前滑动窗口中优美子数组个数
            if (oddCnt == k) {
                // 先将滑动窗口右边界向右拓展,直到遇到下个奇数(或出界)
                // rightEvenCnt即为第k个奇数右边的偶数个数
                int tmp = right;
                while (right < n && (nums[right] & 1) == 0) ++right;
                int rightEvenCnt = right - tmp;
                // leftEventCnt即为第1个奇数左边的偶数个数
                int leftEventCnt = 0;
                while ((nums[left] & 1) == 0) {
                    ++leftEventCnt;
                    ++left;
                }
                // 第1个奇数左边的leftEvenCnt个偶数都可作为优美子数组的起点
                // 因为第1个奇数左边可1个偶数都不取,所以起点的选择有leftEvenCnt + 1 种)
                // 第k个奇数右边的rightEvenCnt个偶数都可作为优美子数组的终点
                // 因为第k个奇数右边可以1个偶数都不取,所以终点的选择有 rightEvenCnt + 1 种)
                // 所以该滑动窗口中,优美子数组左右起点的选择组合数为(leftEvenCnt + 1)*(rightEvenCnt + 1) 
                ans += (leftEventCnt + 1) * (rightEvenCnt + 1);
                // 此时left指向的是第1个奇数,因为该区间已经统计完了,因此left右移一位,oddCnt--
                ++left;
                --oddCnt;
            }
        }
        return ans;
    }
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)

网站文章

  • VS的release模式下,如何使断点生效

    3、连接器——调试——生成调试信息——生成调试信息(/DEBUG)1、c++——常规——调试信息格式——(程序数据库/Zi)2、c++——优化——优化——已禁用。打开项目属性,设置以下内容。

    2024-02-01 04:33:07
  • 华为2018届校招勇敢星实习生招聘笔试+面试经历

    华为2018届校招勇敢星实习生招聘笔试+面试经历

    写在前面  之前一直在忙期末,最近才歇了下来,来总结一下之前参加华为2018届勇敢星实习生笔试+面试(研发类)并顺利拿到offer的经历。   我是在微信上投的Android研发实习生岗,很快就收到...

    2024-02-01 04:33:00
  • C++ 网络编程 TCP 用select实现的并发 异步

    C++ 网络编程 TCP 用select实现的并发 异步

    https://blog.csdn.net/xiyangxiaoguo/article/details/107179169 上一篇采用的是建立新的线程的方法去处理一个新的客户端到服务器的TCP连接,对...

    2024-02-01 04:32:31
  • HTML &amp; CSS 学习总结

    HTML &amp; CSS 学习总结

    一.HTML1.HTML是什么?HTML(超文本标记语言) 是一种用于创建网页结构和内容的标记语言。它是构建互联网世界的基础,被用于描述网页的结构和语义。HTML使用 标签(tag) 来定义文档中的各...

    2024-02-01 04:32:14
  • 时间复杂度 和空间复杂度的计算

    一、 算法的时间复杂度定义 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数...

    2024-02-01 04:32:09
  • Java语言----二叉树 最新发布

    Java语言----二叉树 最新发布

    二叉树详细讲解,以及Java实现代码

    2024-02-01 04:31:41
  • Error: Flutter plugin not installed; this adds Flutter specific functionality. - Flutter

    Error: Flutter plugin not installed; this adds Flutter specific functionality. - Flutter

    安装 Flutter 的时候在 Android Studio IED 处遇到了一些小的插件缺失问题,具体异常提示如下: [!] Android Studio (version 3.4) ✗ Flutter plugin not installed; this adds Flutter specific functionality. ✗ Dart plugin not insta...

    2024-02-01 04:31:36
  • TypeScript 使用let和const声明变量

    使用 let 声明变量 关键字 let 是 ES6 中新增的特性,它的出现是为了解决 var 变量声明所存在的一些问题,let 声明变量的语法和 var 的很像,例如: let a = 1; 其实 l...

    2024-02-01 04:31:27
  • 2020年大厂Java面试前复习的正确姿势(800+面试题答案解析)

    前言个人觉得面试也像是一场全新的征程,失败和胜利都是平常之事。所以,劝各位不要因为面试失败而灰心、 丧失斗志。也不要因为面试通过而沾沾自喜,等待你的将是更美好的未来,继续加油!本篇分享的面试题内容包括:Java、MyBatis、ZooKeeper、Dubbo、Elasticsearch、Redis、MySQL、Spring、SpringBoot、SpringCloud、RabbitMQ...

    2024-02-01 04:31:20
  • Spring,mysql,数据库连接池相关Jar包下载

    Spring,mysql,数据库连接池相关Jar包下载

    自己之前从网上下载使用的一些jar包。现在基本上使用maven导入依赖,所以jar包在网上找起来也很麻烦,自己整合了一些jar包放在网盘里,供下载。主要包括:1.spring-framework-5.0版本的所有jar包2.mysql-connector-java 5.x和8.x版本的jar包3.commons-logging-1.24.commons-beautils-1.945.c3...

    2024-02-01 04:30:52