c1 oa

Question

前两天做了c1 intern oa
总共4题前三题都简单输出形状忘了模拟充电流程
第四题到现在还是没想出来不知道有没大佬解惑
就是给一个int array和int k，要求输出sub array的个数where uniqe element >= k
uniqe element 定义是在这个array里这个元素的频率是1
for example, k = 2,
[1, 2] 是
[1, 2, 1] 不是
[1, 2, 3，1] 是

我的第一反应是用sliding window
但是不确定怎么限制window的扩张和收缩因为两者都可能减少uniqe element的个数
不知道大佬们有没看法或者给个类似力扣题号
感谢

dr · Answer

滑动窗口的题。具体的过程是：初始化窗口左边界left = 0, right = 0, 右移右边界right，同时统计窗口内unique element的数量cnt，当cnt >= k时，表明以left为左边界，以[right, array.size() - 1]为右边界的所有subarray均满足要求，返回值res加上这个subarray的量，即 res += array.size() - right; 然后右移left直到窗口内unique element数量小于k。继续下一步循环。

去LC查了下，类似的一个题目：
2962. Count Subarrays Where Max Element Appears at Least K Times

c1 oa

1 Answers