作者:
Rushia (みけねこ的鼻屎)
2023-09-20 22:26:42https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/descriptio
1658. Minimum Operations to Reduce X to Zero
給你一個陣列 nums 和一個數字 x ,我們每次可以從陣列的最左或最右拿出一個數字
加總並移除該數字,求出最少移除幾個數字後相加會恰好等於 x,如果無法等於 x 返回
-1。
思路:
1.元素只能從陣列的左邊和右邊拿,有拿的部分:left + right,其他部分: mid
nums = [left][mid][right]。
2.我們需要讓 [left] 和 [right] 相加等於 x 且兩者長度盡可能小,也就是中間
部分 [mid] 盡可能大。
3.因為 [left] + [right] = x 且 nums = [left] + [mid] + [right] 所以
[mid] = nums - x,我們可以先用左式把 mid 初始化,如果 [mid] < 0 表示
所有元素相加小於 x,可以直接返回。
4.用滑動窗口的技巧不斷加入元素,如果當前窗口的值 > [mid] 就把左邊的元素
從窗口 pop,如果窗口的值等於 [mid] 就更新結果值。
(nums 長度減去 [mid] 長度)
5.返回結果。
Java Code: