2799. Count Complete Subarrays in an Array

문제

https://leetcode.com/problems/count-complete-subarrays-in-an-array/description/

풀이

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        int answer = 0;

        for(int i = 0; i < n; i++) {
            set.add(nums[i]);
        }

        for(int lt = 0; lt < n; lt++) {
            Set<Integer> target = new HashSet<>();
            for(int rt = lt; rt < n; rt++) {
                target.add(nums[rt]);
                if(set.size() == target.size()) {
                    answer += n - rt;
                    break;
                }
            }
        }
        return answer;
    }
}

• 조건을 만족한다면 오른쪽을 더이상 탐색하지 않아도됨.
• 하지만, lt에 따라 rt를 매번 새롭게 탐색 -> O(n^2)에 가까운 시간복잡도

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        HashMap<Integer, Integer> count = new HashMap<>();
        int answer = 0;

        for(int i = 0; i < n; i++) {
            set.add(nums[i]);
        }

        int size = set.size();
        int lt = 0;

        for(int rt = 0; rt < n; rt++) {
           count.put(nums[rt], count.getOrDefault(nums[rt], 0) + 1);
           while(size == count.size()) {
            answer += n - rt; // 조건을 만족한다면 오른쪽은 전부 complete
            
            count.put(nums[lt], count.get(nums[lt]) - 1); // lt를 1만큼 이동
            if (count.get(nums[lt]) == 0) {
                count.remove(nums[lt]);
            }
            lt++;
           }
        }
        return answer;
    }
}

• lt와 rt가 독립적으로 전진하므로 O(n)