如何获得至少有K个不同数字的子阵列的数量

Question

问题是："给定一个数组A只包含整数。返回至少包含k个不同数字的子数组的数目。子阵列不能重复">

示例：

input array = {1, 2, 3, 4, 2} k = 3
output: 4

说明：

具有至少K个不同数目的子阵列的数目应当是4，它们是[1，2，3][2，3，4][3，4，2][1,2,3,4]

现在我所能做的就是找到具有K个不同数字的子阵列的数量：

class Solution {
public int subarraysWithKDistinct(int[] A, int K) {
return atMostK(A, K) - atMostK(A, K - 1);
}

private int atMostK(int[] A, int K) {
int i = 0, res = 0;

Map<Integer, Integer> count = new HashMap<>();

for (int j = 0; j < A.length; ++j) {

if (count.getOrDefault(A[j], 0) == 0) K--;
count.put(A[j], count.getOrDefault(A[j], 0) + 1);

while (K < 0) {
count.put(A[i], count.get(A[i]) - 1);
if (count.get(A[i]) == 0) K++;
i++;

}
res += j - i + 1;
}

return res;
}
}

但当输入为：array={1,2,3,4,2}k=2我的代码无法正常工作，但我不知道在哪里更改。有什么想法吗？谢谢

更新：感谢@MBo和其他人的回答，我用了2个指针来解决这个问题，但仍然无法得到正确的答案：array={1,2,3,4,2}k=3->输出：6(应该是4(

看起来有一些重复的子字符串需要计数，但我不知道如何修复它

class Solution {
public static void main(String[] args) {
int[] A = {1, 2, 3, 4, 2};
int k = 3;
int res = helper(A, k);
System.out.println(res);
// output is 6, but should be 4
}

private static int helper(int[] A, int k) {
if (A == null || A.length == 0) return 0;

int n = A.length;
int res = 0;
int differentNumbers = 0;
Map<Integer, Integer> counter = new HashMap<>();
int j = 0;  // j - 1 is the right point

for (int i = 0; i < n; i ++) {
while (j < n && differentNumbers < k) {
int numOfThisNumber = counter.getOrDefault(A[j], 0);
counter.put(A[j], numOfThisNumber + 1);
if (counter.get(A[j]) == 1) {
differentNumbers ++;
}
j ++;
}
if (differentNumbers == k) {
res += n - j + 1;
}
counter.put(A[i], counter.get(A[i]) - 1);
if (counter.get(A[i]) == 0) {
differentNumbers --;
}
}
return res; 
}
}

Answer 1

您可以将hashmap方法与两个指针(索引(的方法相结合。

将两个索引都设置为0，并将right移动一个，在间隔的right结束时更新值的哈希图计数，直到哈希图大小达到K。修复right索引。

现在移动left索引，递减与left末尾的值对应的计数。在每个步骤(包括left=0(之前，将size-right添加到结果中，因为从left开始到right结束的所有子数组都包含所需数量的元素。

当某个计数变为0时，从hashmap中移除值，并修复left索引。

用right索引重复，依此类推