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