题目描述
给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?
样例
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
算法1
(双指针) $O(26*n)$
枚举最后的字母c (A-Z), 然后接下来使用双指针方法。
count表示当前需要的花费,把所有字母变成c.
C++ 代码
class Solution {
public:
int characterReplacement(string s, int k) {
int ans = 0;
for (int c = 0; c < 26; ++c) {
unordered_map<char,int> has;
int count = 0;
int i = 0;
for (int j = 0; j < s.size(); ++j) {
if (s[j] != 'A' + c) {
has[s[j]] ++;
count += 1;
}
while (count > k) {
if (s[i] != 'A' + c) {
has[s[i]] --;
count -= 1;
}
i ++;
}
ans = max(ans, j - i + 1);
}
}
return ans;
}
};
这个哈希完全没用,可删掉