时间戳

首页 > 解决方案 > 如何获得至少有 K 个不同数字的子数组的数量？

algorithm - 如何获得至少有 K 个不同数字的子数组的数量？

问题描述

问题是：“给定一个数组 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 -> output: 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; 
    }
}

标签： algorithmsub-array

解决方案

您可以将哈希图方法与两个指针（索引）的方法结合起来。

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

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

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

right用索引等重复。

推荐阅读