LCP-992 K个不同整数的子数组

题目回顾

解法思路

滑动窗口月当然还是用滑动窗口的方法。这题乍一看挺简单,随手就敲了一个$O(n^2)$的双指针遍历方法。果然就卡在了超时上了。

要降低时间复杂度就要让指针不回头,但这时还要找到所有恰好有K种整数的情况并不容易。我们不妨转化下问题,要找到符合条件最长的子串是可以一次遍历求解的。那么一个包含K种数字的最长子串的所有子串均包含$\le K$种数字。

因此可以定义一个函数getMostDistinct(A, K)求得含$\le K$种数字的子串个数,那恰好为K个的情况就等于getMostDistinct(A, K)-getMostDistinct(A, K-1)

思路总结:直接求等不好求的时候,可以将等号条件转化为两个不等关系相减

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
* @lc app=leetcode.cn id=992 lang=cpp
*
* [992] K 个不同整数的子数组
*/

// @lc code=start
class Solution {
public:
int getMostDistinct(vector<int>& A, int K){
int l=0,r=0;
int size=A.size();
int* st=new int[size+1]();
int cnt=0;
int res=0;
while(r<size){
if(st[A[r]]==0){
cnt++;
}
st[A[r]]++;
r++;
while(cnt>K){
st[A[l]]--;
if(st[A[l]]==0){
cnt--;
}
l++;
}
res+=r-l;

}
return res;
}

int subarraysWithKDistinct(vector<int>& A, int K) {
return getMostDistinct(A,K)-getMostDistinct(A,K-1);
}
};
// @lc code=end

时间复杂度O(n) 2 2还是O(n)

LCP-992 K个不同整数的子数组

https://blog.luzy.top/posts/2518194438/

作者

江风引雨

发布于

2021-02-09

更新于

2023-01-10

许可协议

CC BY 4.0

评论