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;
}
};
上一篇: 单链表的基本操作
下一篇: Java学习-常用类(Arrays)