'2025/04/24'에 해당되는 글 1건

Leetcode Problem:

• Count Complete Subarrays in an Array

Summary

• Count the number of complete subarrays in a given array of positive integers.

Approach

• The solution uses a sliding window approach with two unordered maps
• The first map stores the frequency of each element in the array, and the second map stores the frequency of each element in the current subarray
• The time complexity is O(n^2) due to the nested loops, where n is the size of the array.

Complexity

• O(n^2)

Explanation

• The solution first counts the frequency of each element in the array and stores it in the first unordered map
• Then, it iterates over the array with a sliding window approach
• For each window, it creates a new unordered map to store the frequency of each element in the current subarray
• If the size of the current subarray is equal to the size of the first unordered map, it increments the answer by the length of the current subarray plus one (to include the current element)
• Finally, it returns the answer.

Solution Code:

class Solution {
public:
    unordered_map m;
    int countCompleteSubarrays(vector& nums) {
        
        for(int i = 0 ; i < nums.size(); i++){
            m[nums[i]] = true;
        }
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            unordered_map m2;
            for(int j = i; j >= 0; j--){
                m2[nums[j]] = true;
                if(m2.size() == m.size()){
                    ans += j + 1;
                    break;
                }
            }
        }
        return ans;
    }
};