原題鏈接：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.

想法十分地簡單粗暴，遍歷整個(gè)calories array, 用兩指針分別指向一子array的頭和尾钾虐，每次使用一個(gè)private method來遍歷這個(gè)子array獲得sum鞭光，然后判斷該sum與lower bound/upper bound的關(guān)系來累計(jì)得分吏廉。時(shí)間復(fù)雜度是O(N)xO(k)也就是O(N)，空間復(fù)雜度是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;
    }
}

但提交完之后發(fā)現(xiàn)Runtime達(dá)到了649ms席覆，只比18.12% Java solution 快。內(nèi)存占用了45.3MB汹买，少于100%的Java solution佩伤。
參考了一下LeetCode論壇上的答案，發(fā)現(xiàn)還可以優(yōu)化的地方在于：計(jì)算sum的時(shí)候其實(shí)不需要每次都遍歷一次子數(shù)組卦睹，只要把left entry拿掉畦戒，再加入right entry即可。而且因?yàn)樽訑?shù)組的長度是固定的结序，也不需要維護(hù)兩個(gè)指針障斋，只要知道最左或者最右一個(gè)指針就夠了。而且每次都遍歷子數(shù)組的做法也不符合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;
    }
}