leetcode 1248
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
这个问题我认为最直接的思路如我这里的代码所示（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/
继续加油！：）
-
我给我这个代码添加了注释，看看是否能看懂？如果还有问题，请具体指出在哪句话有疑问？https://github.com/liuyubobobo/Play-Leetcode/blob/master/1001-1500/1248-Count-Number-of-Nice-Subarrays/cpp-1248/main.cpp 继续加油！：）
2022-02-06 13:10:12 -
bobo老师非常感谢您, 我看明白您的解法了, 真的机智: ), 我这里有点小问题, 就是我把您的代码用java写了一下但是我这里报了一个错, 我大概明白是table.get(cur) + 1取值的时候取不到所以报错了, 但是我不太明白怎么改成不报错的版本(可能java基础比较菜:>)
2022-02-06 14:53:38
相似问题
登录后可查看更多问答，登录/注册
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧
0 星