1658. Minimum Operations to Reduce X to Zero
給一個整數array : nums 和一個整數 : n
在每次操作可以移除最右邊或最左邊的數字
並且將x扣掉那個數字的值
請回傳最少的操作次數使x剛好被扣到等於0
思路:
假設array所有數字的總和為sum
其實這題換個角度想
就是在問 : 請求一個最長的subarray，該subarray所有數字的總和為sum-x
這樣就用sliding window就可以解決了
c++ :
class Solution {
public:
int minOperations(vector<int> &nums, int x)
{
int sum = 0, n = nums.size(), target = 0, start = 0, cnt = 0;
target = accumulate(nums.begin(), nums.end(), 0) - x;
if (target == 0) {
return n;
}
for (int i = 0; i < n; i++) {
sum += nums[i];
while (start < i && sum > target) {
sum -= nums[start];
start++;
}
if (sum == target) {
cnt = max(cnt, i - start + 1);
}
}
if (cnt == 0) {
return -1;
}
return n - cnt;
}
};

屁眼