LintCode-604: Window Sum (滑动窗口经典题)

滑动窗口的经典题。
解法1：用deque。

    vector<int> winSum(vector<int> &nums, int k) {
        deque<int> dq;
        int sum=0;
        vector<int> result;
        for (int i=0; i<nums.size(); ++i) {
            if (dq.size()<k) {
                dq.push_back(nums[i]);
                sum+=nums[i];
                if (dq.size()==k) result.push_back(sum);
                continue;
            }
            dq.push_back(nums[i]);
            int tmp=dq.front();
            dq.pop_front();
            sum+=nums[i]-tmp;
            result.push_back(sum);
        }
        return result;
    }

解法2：啥都不用，直接用vector。网上的程序。效率很高。

   vector<int> winSum(vector<int> &nums, int k) {
        if (nums.size() < k || k <= 0)
            return vector<int>();

        int n = nums.size();
        vector<int> sums(n - k + 1, 0);

        for (int i = 0; i < k; i++)
            sums[0] += nums[i];
        for (int i = 1; i < n - k + 1; i++) {
            sums[i] = sums[i-1] - nums[i-1] + nums[i + k-1];
        }
        return sums;
    }