前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 992. K 个不同整数的子数组(双指针)

LeetCode 992. K 个不同整数的子数组(双指针)

作者头像
Michael阿明
发布2021-09-07 11:08:50
6380
发布2021-09-07 11:08:50
举报
文章被收录于专栏:Michael阿明学习之路

文章目录

1. 题目

给定一个正整数数组 A,如果 A 的某个子数组中不同整数的个数恰好为 K,则称 A 的这个连续、不一定独立的子数组为好子数组。

(例如,[1,2,3,1,2] 中有 3 个不同的整数:1,2,以及 3。)

返回 A 中好子数组的数目。

代码语言:javascript
复制
示例 1:
输入:A = [1,2,1,2,3], K = 2
输出:7
解释:恰好由 2 个不同整数组成的子数组:
[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2:
输入:A = [1,2,1,3,4], K = 3
输出:3
解释:恰好由 3 个不同整数组成的子数组:
[1,2,1,3], [2,1,3], [1,3,4].
 
提示:
1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/subarrays-with-k-different-integers 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 参考官方思路
  • 每次遍历一个右端点 r,以该右端点为结束的满足题意的子数组有多少个
  • 左端点有两个极限位置 l1, l2,[l1, r]刚好有 k 个不同数字,[l2, r] 刚好有 k-1 个不同数字
  • 累加 满足条件的l2 - l1
代码语言:javascript
复制
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        int l1 = 0, l2 = 0, r = 0, n = A.size();
        int ct1 = 0, ct2 = 0, ans = 0;
        vector<int> nums1(n+1, 0), nums2(n+1, 0);
        while(r < n)
        {
            if(++nums1[A[r]] == 1)
                ct1++;
            if(++nums2[A[r]] == 1)
                ct2++;
            while(ct1 > K)
            {
                if(--nums1[A[l1]] == 0)
                    ct1--;
                l1++;
            }
            while(ct2 >= K)
            {
                if(--nums2[A[l2]] == 0)
                    ct2--;
                l2++;
            }
            ans += l2-l1;
            r++;
        }
        return ans;
    }
};

40 ms 32.5 MB C++


本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/02/09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档