LeetCode 1658. 将 x 减到 0 的最小操作数
原题链接
中等
作者:
wzc1998
,
2023-05-31 12:40:24
,
所有人可见
,
阅读 182
class Solution {
// 逆向思维,最小操作数,就是删的最少,就是留的最多
// 求最长的连续子数组,使得子数组的和恰好为 sum - x
// 对于每一个 i 求最靠左的 j 使得 nums[j~i] 的和 <= sum - x
// 不需要前缀和数组也行,s 维护 nums[j~i] 的和
// 单调性
public int minOperations(int[] nums, int x) {
int sum = 0, res = -1;
for (int num : nums) {
sum += num;
}
if (x > sum) return res;
for (int i = 0, j = 0, s = 0; i < nums.length; i++) {
// s 维护 nums[j~i] 的和
s += nums[i];
// 不断试探
// 注意是 s > sum - x,而不是 s - nums[j] > sum - x
while (s > sum - x) s -= nums[j++];
// j 最多加到 i
// [j, i]
// System.out.println(s + " " + (sum - x));
if (s == sum - x) res = Math.max(res, i - j + 1);
}
return res == -1 ? -1 : nums.length - res;
}
}
有空可以去看一下正向思维的思路