前缀和题目：逐步求和得到正数的最小值

题目

标题和出处

标题：逐步求和得到正数的最小值

出处：1413. 逐步求和得到正数的最小值

难度

2 级

题目描述

要求

给定一个整数数组 $\text{nums}$，选定一个正数 $\text{startValue}$ 作为初始值。

每一轮，将 $\text{startValue}$ 与数组 $\text{nums}$ 中的元素（从左到右）累加求和。

返回最小的正数 $\text{startValue}$，使得累加和总是大于等于 $\text{1}$。

示例

示例 1：

输入：$\text{nums = [-3,2,-3,4,2]}$
输出：$\text{5}$
解释：如果选择 $\text{startValue = 4}$，在第三次累加时，和小于 $\text{1}$。
选择 $\text{startValue = 4}$ 对应的每次累加和依次是：$\text{[1,3,0,4,6]}$。
选择 $\text{startValue = 5}$ 对应的每次累加和依次是：$\text{[2,4,1,5,7]}$。

示例 2：

输入：$\text{nums = [1,2]}$
输出：$\text{1}$
解释：最小的 $\text{startValue}$ 是正数。

示例 3：

输入：$\text{nums = [1,-2,-3]}$
输出：$\text{5}$

数据范围

• $\text{1}\le \text{nums.length}\le \text{100}$
• $\text{-100}\le \text{nums[i]}\le \text{100}$

解法

思路和算法

由于 $\text{startValue}$ 是正整数，因此其最小值是 $1$，将 $\text{startValue}$ 初始化为 $1$。

每个元素的累加和等于 $\text{startValue}$ 加上数组中从首个元素到该元素的所有元素的前缀和，因此从左到右遍历数组，遍历过程中依次计算每个元素的前缀和，并确保累加和总是不小于 $1$。

用 $\text{sum}$ 表示前缀和，从左到右遍历数组的过程中，依次将每个元素加到 $\text{sum}$，则累加和是 $\text{startValue}+\text{sum}$。为了确保累加和总是不小于 $1$，需要确保对于每个元素都满足 $\text{startValue}+\text{sum}\ge 1$，因此需要满足 $\text{startValue}\ge -\text{sum}+1$。每次更新 $\text{sum}$ 的值之后，如果 $\text{startValue}<-\text{sum}+1$，则将 $\text{startValue}$ 的值更新为 $-\text{sum}+1$。遍历结束后，$\text{startValue}$ 即为确保累加和总是不小于 $1$ 的最小值。

由于 $\text{startValue}$ 的初始值为 $1$，每次更新 $\text{startValue}$ 都只会将值增加，因此可以确保 $\text{startValue}$ 是正数。

代码

class Solution {public int minStartValue(int[] nums) {int startValue = 1;int sum = 0;int length = nums.length;for (int i = 0; i < length; i++) {sum += nums[i];startValue = Math.max(startValue, -sum + 1);}return startValue;}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。需要遍历数组一次计算每个元素的前缀和。

• 空间复杂度：$O(1)$。