lintcode 604 · Window Sum (basic)

https://www.lintcode.com/problem/604/

time: O(n)

space: O(n)

public class Solution {
    public int[] winSum(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length) {
            return new int[]{};
        }
        if (k == 0) {
            return new int[nums.length];
        }

        int j = 0; // window's right
        int sum = 0;
        int result[] = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length; i++) { // i is window's left
            while (j < nums.length && j - i < k) { // 持續移動 right
                sum += nums[j];
                j++;
            }
            if (j - i == k) { // 符合窗格大小
                result[i] = sum;
            }
            sum -= nums[i]; // 要到下一個 window 前要減掉當前最左邊的
        }
        return result;
    }
}

反過來寫

public class Solution {
    /**
     * @param nums: a list of integers.
     * @param k: length of window.
     * @return: the sum of the element inside the window at each moving.
     */
    public int[] winSum(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length) {
            return new int[]{};
        }
        if (k == 0) {
            return new int[nums.length];
        }

        int left = 0;
        int sum = 0;
        int result[] = new int[nums.length - k + 1];

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (right - left + 1 > k) {
                sum -= nums[left];
                left++;
            }
            if (right - left + 1 == k) {
                result[left] = sum;
            }
        }
        return result;
    }
}