Instead of re-adding every window from scratch, keep one running sum and slide: add the value that enters on the right, subtract the one that leaves on the left. Each slide costs two operations no matter how wide the window is.
- Average time
- O(n)
- Space
- O(1)