2799.count-complete-subarrays-in-an-array.md

2799. Count Complete Subarrays in an Array

Sliding Window

• 这里计算的是子数组右端点固定的时候，有多少个符合要求的左端点。 while 循环结束时，左端点 = 0,1,2,3,...,left-1 都是满足要求的，这一共有 left 个。
• 因为需要统计的是等于总的数组内的不同元素的个数，所以当出现一个[left, ..., right] 的 subarray 时， [i, ... right] (0 <= i <= left) 和 [left, j] (right <= j <= n) 的 subarray 均成立

Source: https://leetcode.cn/problems/count-complete-subarrays-in-an-array/solutions/2364671/on-hua-dong-chuang-kou-by-endlesscheng-9ztb/

fun countCompleteSubarrays(nums: IntArray): Int {
    val set = HashSet<Int>()
    nums.forEach { set.add(it) }
    val distinct = set.size

    val map = HashMap<Int, Int>()
    var count = 0
    var left = 0
    for (right in nums.indices) {
        map[nums[right]] = (map[nums[right]] ?: 0) + 1
        while (map.size == distinct) {
            // We update the answer here: the number of subarray is lenght of string - remaining elements after right pointer.
            // 这个窗口已经覆盖完全所有可能的元素取值了，那么以r开始往后算所有的num[i]都可以直接加进来，而并不会增加新的元素。因此总共有n-r个可能性。
            count += nums.size - right
            val leftCount = map[nums[left]]!! - 1
            if (leftCount == 0) {
                map.remove(nums[left])
            } else {
                map[nums[left]] = leftCount
            }
            left++
        }
        // Or equivalently.
        // count += left
    }
    return count
}