LeetCode 1658. 将 x 减到 0 的最小操作数
题目描述
思路分析
🔄 本题可以转化为求最长的连续子数组，使得其和为 sum(nums) - x。
因为如果我们找到了这样的一个子数组，那么剩下的元素的和就是 x，也就是我们要减去的值。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func minOperations(nums []int, x int) int {
total := 0
for _, num := range nums {
total += num
}
target := total - x
if target < 0 {
return -1
}
left, right := 0, 0
sum := 0
maxLen := -1
for right < len(nums) {
sum += nums[right]
for sum > target {
sum -= nums[left]
left++
}
if sum == target {
maxLen = max(maxLen, right-left+1)
}
right++
}
if maxLen == -1 {
return -1
}
return len(nums) - maxLen
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！