- 這一是經典的頭尾相連問題,可以透過透過以下手法換轉成簡單的 sliding window
- find
head + tail = x
- let
head + body + tail == total
- the problem becomes FIND
body = total - x
,問題從求最短頭+尾 變成 最長 window
- 套不定長 sliding window。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int total = accumulate(nums.begin(), nums.end(), 0);
int target = total - x;
int left = 0, right = 0, res = -1, n = nums.size();
int curr = 0;
if (target == 0) res = 0; // 注意要處理 boundary condition
while (right < n) {
curr += nums[right++];
while (curr > target && left < right) {
curr -= nums[left++];
}
if (curr == target) {
res = max(res, right-left);
}
}
return res == -1 ? -1 : n - res; // 最後要將長度轉回來
}
};