K 个不同整数子数组

C++ 解法, 执行用时: 25ms, 内存消耗: 3136KB, 提交时间: 2022-07-21

class Solution {
  public:
    int nowsubarray(vector<int>& nums, int k) {
        return mostSubarr(nums, k) - mostSubarr(nums, k - 1);
    }

    int mostSubarr(vector<int>& nums, int k) {
        int H = nums.size();
        vector<int> v(H + 1);
        int z = 0, L = 0, R = 0, c = 0;
        while (R < nums.size()) {
            if (v[nums[R]] == 0) {
                c++;
            }
            v[nums[R]] ++;
            R ++;
            while (c > k) {
                v[nums[L]] --;
                if (v[nums[L]] == 0) {
                    c --;
                }
                L++;
            }
            z += R - L;
        }
        return z;
    }
};

C++ 解法, 执行用时: 25ms, 内存消耗: 3152KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int nowsubarray(vector<int>& nums, int k) {
        return mostSubarr(nums,k)-mostSubarr(nums,k-1);
    }
    int mostSubarr(vector<int> &nums,int k)
    {
        int H=nums.size();
        vector<int> v(H+1);
        int z=0,L=0,R=0,c=0;
        while(R<nums.size())
        {
            if(v[nums[R]]==0)
            {
                c++;
            }
            v[nums[R]]++;
            R++;
            while(c>k)
            {
                v[nums[L]]--;
                if(v[nums[L]]==0)
                {
                    c--;
                }
                L++;
            }
            z+=R-L;
        }
        return z;
    }
};

C++ 解法, 执行用时: 25ms, 内存消耗: 3176KB, 提交时间: 2022-07-12

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int nowsubarray(vector<int>& nums, int k) {
        // write code here
        return mostSubarr(nums, k) - mostSubarr(nums, k - 1);
    }
    
    int mostSubarr(vector<int>& nums, int k){
        int n = nums.size();
        vector<int>freq(n + 1);
        int res = 0, l = 0, r = 0, count = 0;
        while(r < nums.size()){
            if(freq[nums[r]] == 0){
                count ++;
            } 
            freq[nums[r]] ++;
            r ++;
            while(count > k){
                freq[nums[l]] --;
                if(freq[nums[l]] == 0){
                    count --;
                }
                l ++;
            }
            res += r - l;
        }
        return res;
    }
};

C++ 解法, 执行用时: 26ms, 内存消耗: 3164KB, 提交时间: 2022-05-08

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int distance(vector<int> nums, int k) {
        int len = nums.size();
        vector<int> v(len + 1, 0);

        int left = 0;
        int right = 0;
        int count = 0;
        int res = 0;
        while (right < len) {
            if (v[nums[right]] == 0) {
                count += 1;
            }
            v[nums[right]] += 1;
            right += 1;
            
            while (count > k) {
                v[nums[left]] -= 1;
                if (v[nums[left]] == 0) {
                    count -= 1;
                }
                left += 1;
            }
            res += (right - left);
        }
        return res;
    }
    int nowsubarray(vector<int>& nums, int k) {
        // write code here
        return distance(nums, k) - distance(nums, k - 1);
    }
};

C++ 解法, 执行用时: 28ms, 内存消耗: 3148KB, 提交时间: 2022-07-24

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型
     */
    //1,3,1,3,2  
    int nowsubarray(vector<int>& nums, int k) {
        // write code here
        //  把「恰好存在 K 个不同整数的子区间」改成「最多存在 K 个不同整数的子区间」
        //就可以使用双指针一前一后交替向右的方法完成，这是因为 对于每一个确定的左边界，最多包含 K 种不同整数的右边界是唯一确定的，
        //并且在左边界向右移动的过程中，右边界或者在原来的地方，或者在原来地方的右边。
        //而「最多存在 K 个不同整数的子区间的个数」与「恰好存在 K 个不同整数的子区间的个数」的差恰好等于「最多存在 K - 1 个不同整数的子区间的个数」。
        return mostSubarr(nums,k)-mostSubarr(nums,k-1);
    }
    int mostSubarr(vector<int>& nums,int k){
        int l=0,r=0;
        int count=0,res=0;
        vector<int> cnt(nums.size()+1);
        while(r<nums.size()){
            if(cnt[nums[r]]==0) count++;
            cnt[nums[r++]]++;
            while(count>k&&l<r){
                cnt[nums[l]]--;
                if(cnt[nums[l]]==0) count--;
                l++;
            }
            res+=(r-l);
        }
        return res;
    }
};

详情