欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Sliding Window Unique Elements Sum()

程序员文章站 2024-03-05 23:35:37
...

http://www.lintcode.com/zh-cn/problem/sliding-window-unique-elements-sum/?rand=true

import java.util.HashMap;
import java.util.Map;

public class Solution {
    /*
     * @param : the given array
     * @param : the window size
     * @return: the sum of the count of unique elements in each window
     */
    public int slidingWindowUniqueElementsSum(int[] nums, int k) {
        // write your code here
//        用来记录数字,和它出现的次数
        Map<Integer, Integer> map = new HashMap<>();
//        唯一元素的个数
        int count = 0;
//        求和的结果
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
//            这时表明需要删除前边的那个元素了,需要先删除再添加,否则影响重复判断
            if (i >= k) {
                int oldKey = nums[i - k];
                Integer oldValue = map.get(oldKey);
                if (oldValue == 1) {
//                    如果里边只有它一个元素,删除后,唯一的个数需要减1
                    map.remove(oldKey);
                    count--;
                } else {
//                    如果它的个数大于1,删除后,个数减1,如果减去之后等于1,说明它变成唯一了,唯一个数加1
                    map.put(oldKey, oldValue - 1);
                    if (oldValue - 1 == 1) {
                        count++;
                    }
                }
            }
            int key = nums[i];
            int value = 1;
            if (map.containsKey(key)) {
//                如果map中已经有它了,个数加1,如果原来它的个数是1,说明它由唯一变成重复了,唯一个数减1
                value = map.get(key) + 1;
                if (value == 2) {
                    count--;
                }
            } else {
//                没有的时候,唯一个数直接加1
                count++;
            }
            map.put(key, value);
            if (i >= k - 1) {
//                每次有k个元素时,把唯一个数加到结果中。
                res += count;
            }
        }
//        这是个坑,如果所有的元素都不到k个时,返回count
        if (res == 0) {
            return count;
        }
        return res;
    }
};