Window Sum

// Given an list of number and a window size k,  return a list contains sum of all windows.
import java.util.List;
import java.util.ArrayList;

/**
 * Created by RuiG on 11/19/16.
 */
public class WindowSum {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9};
        List<Integer> list = new ArrayList<>();
        for (int num: nums) {
            list.add(num);
        }
        System.out.println(list);
        List<Integer> ans = windowSum(list, 3);
        System.out.println(ans);
    }

    public static List<Integer> windowSum(List<Integer> list, int k) {
        List<Integer> ans = new ArrayList<>();
        // corner case
        if (list == null || list.size() == 0 || list.size() < k) {
            return ans;
        }
        // use dp to avoid redundant compute
        int n = list.size();
        int[] dp = new int[n - k];
        // init dp[0]
        for (int i = 0; i < k; i++) {
            dp[0] += list.get(i);
            ans.add(dp[0]);
        }
        // build dp[] array
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i - 1] - list.get(i - 1) + list.get(i - 1 + k);
            ans.add(dp[i]);
        }
        return ans;
    }
}