ZS_2461_长度为K子数组中的最大和

思路

滑动窗口 + Map 维护元素出现次数， 然后遍历一遍即可求出答案

滑动窗口

滑动窗口是双指针的一种特例，任意时刻只有一个指针在运动，另一个指针静止，指针包含区域称为窗口，指针的运动即窗口的滑动。

滑动窗口的时间复杂度是线性的，一般为O(n)。

滑动窗口一般用于解决特定的序列中符合条件的连续的子序列的问题。这个序列大多数是指数组或者字符串。

Java-Map

Java集合类Map，Map集合类用于存储元素对( key : value )，每个键对映一个值，key值如果相等的话会把之前存放的值覆盖，其内部元素不会重复。

解法

    public long maximumSubarraySum(int[] nums, int k) {
        int len = nums.length;
        long res = 0, sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        //初始化Map和sum，避免最初的k个数中出现重复值
        for (int i = 0; i < k; i++) {
            sum += nums[i];
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        if (map.size() == k)
            res = Math.max(res, sum);
        for (int i = k; i < len; i++) {
            //右指针右移
            sum += nums[i];
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            //左指针右移
            sum -= nums[i - k];
            int cnt = map.get(nums[i - k]);
            if (cnt == 1)
                map.remove(nums[i - k]);
            else
                map.put(nums[i - k], cnt - 1);
            if (map.size() == k) {
                res = Math.max(res, sum);
            }
        }
        return res;
    }

hashmap.put(K key, V value),插入操作，如果插入的key值已经存在？执行value替换操作，返回旧value值：不存在则执行插入操作，返回null

hashmap.getOrDefault(Object key, V defaultValue),返回key相映射value值，若给定的key无法找到则返回指定的默认值

hashmap.get(Object key),返回给定key相映射的value

原文地址：http://www.cnblogs.com/Pilo-pillow/p/16879775.html