leetcode 1248

首页课程实战体系课手记专栏慕课教程

leetcode 1248

来源：1-1 哈希表基础

weixin_慕圣6334738

2022-02-04 09:40:55

bobo老师你好,想请教下您leetcode1248题怎么做?

discussion里面有一个这样的解法, 但是我没明白它是什么意思~

相关代码：

  public int numberOfSubarrays(int[] A, int k) {        return atMost(A, k) - atMost(A, k - 1);
    }    public int atMost(int[] A, int k) {        int res = 0, i = 0, n = A.length;        for (int j = 0; j < n; j++) {
            k -= A[j] % 2;            while (k < 0)
                k += A[i++] % 2;
            res += j - i + 1;
        }        return res;
    }

感谢您的解答!

写回答

1回答

liuyubobobo

2022-02-05

这个问题我认为最直接的思路如我这里的代码所示（C++ 写的，但思路应该能看懂）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/1001-1500/1248-Count-Number-of-Nice-Subarrays/cpp-1248/main.cpp

即：遍历每一个元素，作为区间的右边界，我们可以一直跟踪从 0 到当前的右边界 r，一共有多少个奇数，记为cur；之后只要减去这个右边界左侧，有多少左边界，其左边的奇数个数位 cur - k 个即可。

记录从 0 到一个元素一共有多少个奇数使用哈希表。

==========

上面的做法空间是 O(n) 的，你给出的代码空间是 O(1) 的，更加巧妙一点（但我不认为算法面试需要想到这个解）。我个人认为我的代码更易懂（同一个思路）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/1001-1500/1248-Count-Number-of-Nice-Subarrays/cpp-1248/main2.cpp

其中，f(nums, k) 求的是，nums 中有多少个区间，其奇数个数 <= k。所以，f(nums, k) - f(nums, k - 1) 就是 nums 中有多少个区间其奇数个数恰好是 k。

具体 f 的逻辑是用的是滑动窗口。如果你了解滑动窗口，f 的这个逻辑应该比较好理解。如果不了解的话，我的这个课程专门有一章讲滑动窗口：https://coding.imooc.com/class/82.html （不过这个课程视频中使用的是 C++）。

如果没有购买也没有关系，滑动窗口是非常经典的一类思路，力扣中有专门一个标签，就是滑动窗口。你可以看看这个标签下的问题，研究一下相应题解的写法：https://leetcode-cn.com/tag/sliding-window/problemset/

继续加油！：）

hiuyubobobo

heixin_慕圣6334738

hp>最简单的方法是写一个 if else：

```

if(table.containsKey(cur))

table.put(cur, table.get(cur) + 1);

else

table.put(cur, 1);