1176. Diet Plan Performance

原题链接：Diet Plan Performance
LeetCode 最简单的Sliding Window题目。

A dieter consumes calories[i] calories on the i-th day.
Given an integer k, for every consecutive sequence of k days (calories[i], calories[i+1], ..., calories[i+k-1] for all 0 <= i <= n-k), they look at T, the total calories consumed during that sequence of k days (calories[i] + calories[i+1] + ... + calories[i+k-1]):
If T < lower, they performed poorly on their diet and lose 1 point;
If T > upper, they performed well on their diet and gain 1 point;
Otherwise, they performed normally and there is no change in points.
Initially, the dieter has zero points. Return the total number of points the dieter has after dieting for calories.length days.
Note that the total points can be negative.

想法十分地简单粗暴，遍历整个calories array, 用两指针分别指向一子array的头和尾，每次使用一个private method来遍历这个子array获得sum，然后判断该sum与lower bound/upper bound的关系来累计得分。时间复杂度是O(N)xO(k)也就是O(N)，空间复杂度是O(1)。

class Solution {
    public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
        if (calories == null || calories.length < k || k == 0
           || lower > upper) {
            return 0;
        }
        
        int score = 0;
        int start = 0;
        int end = k - 1;
        while (end < calories.length) {
            int total = sumUpCalories(start, end, calories);
            if (total < lower) {
                score--;
            } else if (total > upper) {
                score++;
            }
            start++;
            end++;
        }
        
        return score;
    }
    
    private int sumUpCalories (int start, int end, int[] calories) {
        int total = 0;
        for (int i = start; i <= end; i++) {
            total += calories[i];
        }
        
        return total;
    }
}

但提交完之后发现Runtime达到了649ms，只比18.12% Java solution 快。内存占用了45.3MB，少于100%的Java solution。
参考了一下LeetCode论坛上的答案，发现还可以优化的地方在于：计算sum的时候其实不需要每次都遍历一次子数组，只要把left entry拿掉，再加入right entry即可。而且因为子数组的长度是固定的，也不需要维护两个指针，只要知道最左或者最右一个指针就够了。而且每次都遍历子数组的做法也不符合sliding window的基本思想吧（我猜）。
改良之后版本Runtime降到了1ms。Memory usage pretty much stays the same.

class Solution {
    public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
        if (calories == null || calories.length < k || k == 0
           || lower > upper) {
            return 0;
        }
        
        int score = 0;
        int total = 0;
        int start = 0;
        
        for (int i = 0; i < k; i++) {
            total += calories[i];
        }
        if (total < lower) {
            score--;
        }
        if (total > upper) {
            score++;
        }
        
        for (int i = k; i < calories.length; i++) {
            total += calories[i];
            total -= calories[start++];
            
            if (total < lower) {
                score--;
            }
            if (total > upper) {
                score++;
            }
        }
        
        return score;
    }
}