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

目录

题目链接：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: 计算整个数组的不同元素数目 totalDistinctint 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);// 收缩窗口，直到窗口内的不同元素数目等于 totalDistinctwhile (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] <= 2000int 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)); // 输出: 4int[] 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: 计算整个数组的不同元素数目 totalDistinctint 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]]++;// 收缩窗口，直到窗口内的不同元素数目等于 totalDistinctwhile (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] <= 2000int 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; // 输出: 4vector<int> nums2 = {5, 5, 5, 5};cout << solution.countCompleteSubarrays(nums2) << endl; // 输出: 10return 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. 其他变量：

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