题目描述

题目描述

分析题目，子数组中不同元素的数目等于整个数组中不同元素的数目，因此，子数组中含有的不同元素一定与整个数组中含有的不同元素完全一样。可以使用两个哈希表，一个表放入整个数组的元素，另一个表放入子数组的元素，如果两个表的大小相同，那么该子数组就是完全子数组。

算法1—暴力求解

我们遍历整个数组中的所有子数组，来判断子数组的哈希表大小是否与整个数组的哈希表大小相同

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        int ans=0;
        HashSet<Integer> set=new HashSet<Integer>();
        for(int i:nums) set.add(i);
        for(int i=0;i<nums.length;i++){
            for(int j=i;j<nums.length;j++){
                HashSet<Integer> newSet=new HashSet<Integer>();
                for(int k=i;k<=j;k++){
                    newSet.add(nums[k]);
                }
                if(set.size()==newSet.size()) ans++;
                newSet.clear();
            }
        }
        return ans;
    }
}

该方法最外层循环i从0到nums.length-1共n次，内层循环j从i到nums.length-1约n/2次，最内层循环k从i到j平均约n/2次，因此总次数约为n(n/2)(n/2)。
时间复杂度为O（n³），空间复杂度为O（n）。

算法2—滑动窗口

可以使用滑动窗口来统计满足条件的子数组，具体来说，维护一个[left,right]的窗口，动态调整left和right，以确保窗口内包含原数组的所有数组种类。

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        int ans=0;
        HashSet<Integer> set=new HashSet<Integer>();
        for(int i:nums) set.add(i);
        for(int i=0;i<nums.length;i++){
            HashSet<Integer> newSet=new HashSet<Integer>();
            for(int j=i;j<nums.length;j++){
                newSet.add(nums[j]);
                if(newSet.size()==set.size()) {
                    // 当前窗口内已经包含所有原数组中元素的种类
                    // 那么加入窗口右端j后面的所有元素也一定包含所有元素种类
                    ans+=nums.length-j;
                    break;
                }
            }
        }
        return ans;
    }
}

时间复杂度O（n²），空间复杂度O（n）。

算法3—滑动窗口和哈希表优化

可以使用一个哈希表记录滑动窗口中数字出现的次数，避免重复统计

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        HashSet<Integer> set=new HashSet<Integer>();
        for(int i:nums) set.add(i);
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        int left=0,ans=0;
        for(int right=0;right<nums.length;right++){
            map.put(nums[right],map.getOrDefault(nums[right],0)+1);
            // 如果当前窗口中含有所有种类的数字
            // 后续窗口右边的所有数字也都符合
            while(map.size()==set.size()) {
                ans+=nums.length-right;
            // 尝试移动左边界left，缩小窗口
                map.put(nums[left],map.get(nums[left])-1);
                if(map.get(nums[left])==0){
                    map.remove(nums[left]);
                }
                left++;
            }
        }
        return ans;
    }
}

统计set时遍历一遍nums数组，时间复杂度O（n），right从0到nums.length-1，left最多也从0到nums.length-1，因此每个数字最多被left和right访问两次（加入和移出map）。
时间复杂度O（n），空间复杂度O（n）。