LEETCODE 1176. Diet Plan Performance 解题思路分析

题目大意：

健身计划评估

calories[i] 给出了健身者在第 i 天需要消耗的卡路里总量，对于每连续的 k 天，消耗的总卡路里为 T：

• 如果 T < lower，那么这份计划相对糟糕，并失去 1 分；
• 如果 T > upper，那么这份计划相对优秀，并获得 1 分；
• 否则，分值不做变动。

请返回统计完所有 calories.length 天后得到的总分作为评估结果。

注意：总分可能是负数。

示例1：

输入：calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
输出：0
解释：calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 总分 = 0.

示例2：

输入：calories = [3,2], k = 2, lower = 0, upper = 1
输出：1
解释：calories[0] + calories[1] > upper, 总分 = 1.

示例3：

输入：calories = [6,5,0,0], k = 2, lower = 1, upper = 5
输出：0
解释：calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, 总分 = 0.

提示：

• 1 <= k <= calories.length <= 10^5
• 0 <= calories[i] <= 20000
• 0 <= lower <= upper

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1176

解题思路分析：

将题目简单的翻译一下，就是要求出所有连续区间长度为k的和，如果和大于 upper 加一分，若小于 lower 减一分。求最后的总分数。

对于连续区间求和问题，我们应该想到使用前缀和数组preSum[]，先遍历一遍数组，求出每个元素到首元素区间内所有元素之和，然后如果想求出任意区间的和，

sum[i,j] = preSum[j]-preSum[i-1];

实现代码：

public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
    int[] preSum = new int[calories.length+1]; // 前缀和数组
    for(int i=0;i<calories.length;i++){ // 计算前缀和
        preSum[i+1]=preSum[i]+calories[i];
    }
    int res=0; // 返回结果
    for(int i=k;i<preSum.length;i++){
        // 计算以下标i结尾并长度为k区间的和
        int consume = preSum[i]-preSum[i-k];
        // 若和小于lower，结果减一
        if(consume<lower) res--;
        // 若和大于upper，结果加一
        if(consume>upper) res++;
    }
    return res;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 66.92% of Java online submissions for Diet Plan Performance.

Memory Usage: 45.8 MB, less than 100.00% of Java online submissions for Diet Plan Performance.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1176-diet-plan-performance-解题思路分析/