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

LINTCODE——Sliding Window Unique Elements Sum

程序员文章站 2024-03-06 08:43:43
...

LINTCODE——Sliding Window Unique Elements Sum

问题:Given an array and a window size that is sliding along the array, find the sum of the count of unique elements in each window.

思路:总体来说不算太难,用一个map进出一个记录一下差值就ok了

class Solution {
public:
    /*
     * @param : the given array
     * @param : the window size
     * @return: the sum of the count of unique elements in each window
     */
    int slidingWindowUniqueElementsSum(vector<int> nums, int k) {
        // write your code here

        int n = nums.size();
        map<int, int> record;
        for(int i = 0 ; i < min(k,n); i++)
            record[nums[i]]++;
        vector<int> res;
        res.push_back(count(record));

        for(int i = k; i < n ; i++)
        {
            int temp = 0;
            record[nums[i-k]]--;
            record[nums[i]]++;
            if(nums[i-k] != nums[i]){
                if(record[nums[i-k]] == 1)
                    temp++;
                else if(record[nums[i-k]] == 0)
                    temp--;

                if(record[nums[i]] == 1)
                    temp++;
                else if(record[nums[i]] == 2)
                    temp--;
            }
            res.push_back(res[i-k]+temp);

        }
        int ret = 0;
        for(int x : res)
            ret += x;

        return ret;
    }
    int count(map<int, int> &record)
    {
        int num = 0;
        for(auto x : record)
        {
            if(x.second == 1)
                num++;
        }
        return num;
    }
};