Saturday, January 14, 2017

Window Sum

Given a list of integers, and a window size k, the window slides from left to right. Calculate the sum of integers in the window in each slide.

For example:
Given: A = [1,2,2,-3,4,0,3], k = 3. 
Return: [5, 1, 3, 1, 7]

/*
Two pointers, maintain a window whose size is k.
time:O(n), space:O(1)
*/

import java.util.*;

public class Solution {
    public static List<Integer> GetSum(List<Integer> A, int k) {
        ArrayList<Integer> res  = new ArrayList<>();
        if (A == null || A.size() == 0 || k <= 0) {
            return res;
        }
        int i = 0, j = 0;
        int sum = 0;
        for (i = 0; i < A.size() - k + 1; i++) {
            while (j < A.size() && j - i < k) {
                sum += A.get(j);
                j++;
            }
            res.add(sum);
            sum -= A.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        List<Integer> A = new ArrayList<>();
        A.add(1);
        A.add(1);
        A.add(2);
        A.add(-4);
        A.add(5);
        A.add(0);
        List<Integer> ans = GetSum(A, 7);
        for (Integer i : ans) {
            System.out.print(i + " ");
        }
    }
}

No comments:

Post a Comment