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;
}
};

屁眼