力扣热题——统计完全子数组的数目

目录

题目链接：2799. 统计完全子数组的数目 - 力扣（LeetCode）

题目描述

解法一：滑动窗口 + 哈希表

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

时间复杂度

空间复杂度

题目链接：2799. 统计完全子数组的数目 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给你一个由 正 整数组成的数组 nums 。

如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：

• 子数组中 不同 元素的数目等于整个数组不同元素的数目。

返回数组中 完全子数组 的数目。

子数组 是数组中的一个连续非空序列。

示例 1：

输入：nums = [1,3,1,2,2]
输出：4
解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。

示例 2：

输入：nums = [5,5,5,5]
输出：10
解释：数组仅由整数 5 组成，所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2000

解法一：滑动窗口 + 哈希表

1. 滑动窗口 + 哈希表：

   • 使用滑动窗口来枚举所有可能的子数组。
   • 使用哈希表（或数组）来记录当前窗口内的不同元素及其出现次数。
   • 动态调整窗口大小，确保窗口内的不同元素数目等于整个数组的不同元素数目。

2. 优化计算：

   • 先计算出整个数组的不同元素数目 totalDistinct。
   • 滑动窗口的过程中，一旦窗口内的不同元素数目等于 totalDistinct，就可以快速统计以当前右边界为终点的所有合法子数组。

3. 复杂度分析：

   • 时间复杂度：O(n)，其中 n 是数组长度。每个元素最多被左右指针访问两次。
   • 空间复杂度：O(k)，其中 k 是数组中不同元素的最大数目（题目限制 k ≤ 2000）。

Java写法：

import java.util.HashMap;

public class Solution {
    public int countCompleteSubarrays(int[] nums) {
        // Step 1: 计算整个数组的不同元素数目 totalDistinct
        int totalDistinct = countDistinct(nums);

        // Step 2: 使用滑动窗口统计完全子数组的数目
        int n = nums.length;
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        int left = 0, right = 0;
        int result = 0;

        while (right < n) {
            // 扩展窗口，将 nums[right] 加入窗口
            freqMap.put(nums[right], freqMap.getOrDefault(nums[right], 0) + 1);

            // 收缩窗口，直到窗口内的不同元素数目等于 totalDistinct
            while (freqMap.size() == totalDistinct) {
                // 统计以当前 right 为右边界的所有合法子数组
                result += n - right;

                // 移除左边界元素
                freqMap.put(nums[left], freqMap.get(nums[left]) - 1);
                if (freqMap.get(nums[left]) == 0) {
                    freqMap.remove(nums[left]);
                }
                left++;
            }

            // 移动右边界
            right++;
        }

        return result;
    }

    // 辅助函数：计算数组中的不同元素数目
    private int countDistinct(int[] nums) {
        boolean[] seen = new boolean[2001]; // 根据题目限制，nums[i] <= 2000
        int distinctCount = 0;
        for (int num : nums) {
            if (!seen[num]) {
                seen[num] = true;
                distinctCount++;
            }
        }
        return distinctCount;
    }

    // 测试用例
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1, 3, 1, 2, 2};
        System.out.println(solution.countCompleteSubarrays(nums1)); // 输出: 4

        int[] nums2 = {5, 5, 5, 5};
        System.out.println(solution.countCompleteSubarrays(nums2)); // 输出: 10
    }
}

C++写法：

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        // Step 1: 计算整个数组的不同元素数目 totalDistinct
        int totalDistinct = countDistinct(nums);

        // Step 2: 使用滑动窗口统计完全子数组的数目
        int n = nums.size();
        unordered_map<int, int> freqMap;
        int left = 0, right = 0;
        int result = 0;

        while (right < n) {
            // 扩展窗口，将 nums[right] 加入窗口
            freqMap[nums[right]]++;

            // 收缩窗口，直到窗口内的不同元素数目等于 totalDistinct
            while (freqMap.size() == totalDistinct) {
                // 统计以当前 right 为右边界的所有合法子数组
                result += n - right;

                // 移除左边界元素
                freqMap[nums[left]]--;
                if (freqMap[nums[left]] == 0) {
                    freqMap.erase(nums[left]);
                }
                left++;
            }

            // 移动右边界
            right++;
        }

        return result;
    }

private:
    // 辅助函数：计算数组中的不同元素数目
    int countDistinct(const vector<int>& nums) {
        vector<bool> seen(2001, false); // 根据题目限制，nums[i] <= 2000
        int distinctCount = 0;
        for (int num : nums) {
            if (!seen[num]) {
                seen[num] = true;
                distinctCount++;
            }
        }
        return distinctCount;
    }
};

// 测试用例
int main() {
    Solution solution;
    vector<int> nums1 = {1, 3, 1, 2, 2};
    cout << solution.countCompleteSubarrays(nums1) << endl; // 输出: 4

    vector<int> nums2 = {5, 5, 5, 5};
    cout << solution.countCompleteSubarrays(nums2) << endl; // 输出: 10

    return 0;
}

运行时间

时间复杂度和空间复杂度

时间复杂度

1. 计算不同元素数量 countDistinct：

   • 这个过程需要遍历整个数组一次，因此时间复杂度是 O(n)，其中 n 是数组的长度。

2. 滑动窗口主循环：

   • 主循环中，右指针 right 从数组的开始到结束进行遍历，即最多遍历 n 次。
   • 在最坏情况下，左指针 left 也会遍历整个数组。但是每个元素最多被左右指针各访问一次，所以这部分操作的时间复杂度也是 O(n)。
   • 因此，整个滑动窗口部分的时间复杂度为 O(n)。

3. 综合考虑：

   • 计算不同元素数量加上滑动窗口的过程，总的时间复杂度是 O(n) + O(n) = O(n)。

空间复杂度

1. 存储不同元素的状态 seen：

   • 使用了一个大小为 2001 的布尔数组（根据题目限制 nums[i] <= 2000），用于标记每个数字是否出现过。空间复杂度为 O(k)，其中 k 是数组中不同元素的最大数目，在这里 k 最大为 2000。

2. 哈希表 freqMap：

   • 哈希表用于记录当前窗口内每个元素的频率。在最坏情况下，哈希表可能包含所有不同的元素。因此，空间复杂度也是 O(k)，k 同上。

3. 其他变量：

   • 其他使用的额外空间（如整数变量）相对于输入规模来说是常数级别的，不影响总体的空间复杂度分析。