K 个不同整数子数组

[编程题]K 个不同整数子数组

热度指数：451 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的正整数数组 nums 和一个目标整数 k ，返回数组中的牛连续子数组的数目。

如果 nums 中的某个连续子数组中不同的整数个数恰好是 k 个，则称这个连续子数组为牛连续子数组，不同位置的连续子数组可能一样，都算入最终数目里。

数据范围： $1 \le nums_i , k \le n \le 10^5 \$

示例1

输入

[1,3,1,3,2],2

输出

说明

七个牛连续子数组是 [1,3] , [3,1] , [1,3] , [3,2] , [1,3,1] , [3,1,3] , [1,3,1,3]

示例2

输入

[1,1,4,5,1,4],2

输出

说明

[1,4],[4,5],[5,1],[1,4],[1,1,4]

算法知识视频讲解

Java

唐氏综合征

首先声明一下，这道题思路真的很难，最开始我也想到了滑动窗口加双指针，但是处理窗口左边界时只能计算出当前遍历的最长的包含k个不重复元素的子串的数量，这个子串里面又有多重组合也满足条件，却无法计算出来，比如

[1,3,1,3,2],2 只能得到 [1,3], [1,3,1], [1,3,1,3] ，却没办法得到 [3,1,3], [1,3] 这样的串, 使用双层 for 循环+双指针是可以解决的，只需要让右指针每次循环都从左指针开始，但是效率太低，看了一下别人的见解，可以吧这个问题拆分为：最多包含k个不重复元素的子串减去最多包含 k-1 个不重复元素的子串 = 恰好包含k个不重复元素的子串具体思路如下：

1. 计算出最多包含 k 个不重复元素的子串

2. 计算出最多包含 k -1 个不重复元素的子串

3. 上述两者相减则为最终答案

注意：需要注意的是，计算最多包含k个不重复子串的代码中 ,当右边指针变化时(j++)

后，每次的 j 的变动，都要重新计算子数组的数量，以新的 j 结尾的子数组数量就等于 j - i, 因此所有的组合就是每次不同的 j结尾的子串之和，也就是 ret += j-i 这是难点：

  // 使用滑动窗口解决
    public static int nowsubarray (ArrayList<Integer> nums, int k) {
        // write code here
        return help(nums, k) - help(nums, k - 1);
    }


    private static int help(ArrayList<Integer>nums, int k) {
        int i = 0, j = 0;
        Map<Integer, Integer> cnt = new HashMap<>(); // Records the frequency of integers in the [i, j) interval
        int ret = 0;

        while (j < nums.size()) {
            cnt.put(nums.get(j), cnt.getOrDefault(nums.get(j), 0) + 1);
            j++;

            while (cnt.size() > k) {
                cnt.put(nums.get(i), cnt.get(nums.get(i)) - 1);
                if (cnt.get(nums.get(i)) == 0) {
                    cnt.remove(nums.get(i));
                }
                i++;
            }
            // 每次的 j 的变动，都要重新计算子数组的数量，以新的 j 结尾的子数组数量就等于 j - i
            ret += j - i;
        }

        return ret;
    }

使用双层for循环+双指针解法不推荐，略.

发表于 2024-05-07 17:36:17 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-

import collections


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @param k int整型
# @return int整型
#
class Solution:
    """
    题目;
        https://www.nowcoder.com/practice/ac380725961a46a2b0747f803f96d6e7?tpId=196&tqId=40551&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        https://leetcode.cn/problems/subarrays-with-k-different-integers/solution/k-ge-bu-tong-zheng-shu-de-zi-shu-zu-by-l-ud34/
    算法：
        题目要求：统计nums中 不同字符数为k的连续子数组 的个数
        我们对于原问题进行转换：
            把「恰好存在 K 个不同整数的子区间」改成「最多存在 K 个不同整数的子区间」就可以使用双指针一前一后交替向右的方法完成，这是因为 对于每一个确定的左边界，最多包含 K 种不同整数的右边界是唯一确定的，并且在左边界向右移动的过程中，右边界或者在原来的地方，或者在原来地方的右边。
            而「最多存在 K 个不同整数的子区间的个数」与「恰好存在 K 个不同整数的子区间的个数」的差恰好等于「最多存在 K - 1 个不同整数的子区间的个数」。
        使用双指针（滑动窗口）：定义函数atMostKDistinct(nums, k)表示「最多存在 K 个不同整数的子区间的个数」
        返回值：
            atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1)
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(k)
    """

    def nowsubarray(self, nums, k):
        # write code here
        def atMostKDistinct(k):
            left, right, n = 0, 0, len(nums)
            distinct, res, count = 0, 0, collections.Counter()

            while right < n:
                if count[nums[right]] == 0:
                    distinct += 1
                count[nums[right]] += 1
                while distinct > k:
                    count[nums[left]] -= 1
                    if count[nums[left]] == 0:
                        distinct -= 1
                    left += 1
                res += right - left + 1 # 区间[left, right]上以下标left为起点的子区间有right - left + 1个
                right += 1
            return res

        return atMostKDistinct(k) - atMostKDistinct(k - 1)

if __name__ == "__main__":
    sol = Solution()

    nums, k = [1, 3, 1, 3, 2], 2

    # nums, k = [1, 1, 4, 5, 1, 4], 2

    # nums, k = [1, 3, 1], 2

    res = sol.nowsubarray(nums, k)

    print res

发表于 2022-07-08 14:27:26 回复(0)