LeetCode-2537 统计好子数组的数目

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。

一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。

子数组 是原数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。

示例 2：

输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：总共有 4 个不同的好子数组：
- [3,1,4,3,2,2] 有 2 对。
- [3,1,4,3,2,2,4] 有 3 对。
- [1,4,3,2,2,4] 有 2 对。
- [4,3,2,2,4] 有 2 对。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i], k <= 10^9

题解——动态规划

超出内存限制

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        // 至少 k 对下标
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(int i = 0; i < n; i ++){
            unordered_map<int, int> ump;
            ump[nums[i]] = 1;
            for(int j = i + 1; j < n; j ++){
                if(ump.find(nums[j]) != ump.end()){
                    dp[i][j] = ump[nums[j]] + dp[i][j - 1];
                    ump[nums[j]] ++;
                }
                else{
                    dp[i][j] = dp[i][j - 1];
                    ump[nums[j]] = 1;
                }
            }
        }
        // for(int i = 0; i < n; i ++){
        //     for(int j = 0; j < n; j ++){
        //         cout << dp[i][j] <<' ';
        //     }
        //     cout << endl;
        // }
        int res = 0;
        for(int i = 0; i < n; i ++){
            for(int j = i + 1; j < n; j ++){
                if(dp[i][j] >= k) res ++;
            }
        }
        return res;
    }
};

超出时间限制

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        // 至少 k 对下标
        int n = nums.size();
        long long res = 0;
        vector<int> dp(n, 0);
        for(int i = 0; i < n; i ++){
            unordered_map<int, int> ump;
            ump[nums[i]] = 1;
            for(int j = i + 1; j < n; j ++){
                if(ump.find(nums[j]) != ump.end()){
                    dp[j] = ump[nums[j]] + dp[j - 1];
                    ump[nums[j]] ++;
                }
                else{
                    dp[j] = dp[j - 1];
                    ump[nums[j]] = 1;
                }
                if(dp[j] >= k){ // 剪枝
                    res += n - j;
                    break;
                }
            }
        }
        return res;
    }
};

题解——双指针

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        // 至少 k 对下标
        int n = nums.size();
        long long res = 0;
        int right = 0;
        int count = 0;
        unordered_map<int, int> ump;
        for(int left = 0; left < n; left ++){
            while(count < k && right < n){
                count += ump[nums[right]];
                ump[nums[right]] ++;
                right ++;
            }
            if(count >= k){
                res += n - right + 1;
            }
            ump[nums[left]] --;
            count -= ump[nums[left]];
        }
        return res;
    }
};