如何获取至少有 K 个不同数字的子数组的编号？

Question

问题是： “给定数组 A 仅包含整数 Return 包含至少 k 个不同数字的子数组的数量。子数组不能重复。”

示例：

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

output: 4

解释：

至少有K个不同数的Subarray的个数应该是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;
    }
}

但是当输入是：数组 = {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 索引等。

如何获取至少有 K 个不同数字的子数组的编号？

How to get the number of the Subarray with at least K different numbers?

algorithm

sub-array