leetcode 1658. 将 x 减到 0 的最小操作数-Minimum Operations to Reduce X to Zero

Problem: 1658. 将 x 减到 0 的最小操作数-Minimum Operations to Reduce X to Zero

求出前缀数组，以及后缀数组，然后对遍历后缀数组，对每个数字，二分查找 a=x - addfix[i]，然后若满足 ind < i && prefix[ind]==a，求出最小值：mi = min(mi, n - i + 1 + ind);

最后返回最小值即可

Code

class Solution { public: int minOperations(vector<int>& nums, int x) { int n = nums.size(); vector<int> prefix{0}, addfix(n+2, 0); for(int& i : nums) prefix.push_back(prefix.back() + i); for(int i = n; i >= 1; i--) { addfix[i] = addfix[i+1] + nums[i-1]; } int ind, a, mi = INT_MAX; for(int i = n+1; i >= 1; i--) { a = x - addfix[i]; if(a < 0) break; if(a == 0) { mi = min(mi, n - i + 1); continue; } else if(a >= nums[0]) { ind = lower_bound(prefix.begin(), prefix.end(), a) - prefix.begin(); if(ind < i && prefix[ind] == a) { mi = min(mi, n - i + 1 + ind); } } } if(mi == INT_MAX) return -1; return mi; } };

方案2

class Solution { public: int minOperations(vector<int>& nums, int x) { int n = nums.size(), s = 0, ind, a, mi = INT_MAX; vector<int> prefix{0}, addfix(n+2, 0); for(int& i : nums) { s += i; prefix.push_back(s); } for(int i = 0; i <= n; i++) { a = x - (s - prefix[i]); if(a >= 0) { ind = lower_bound(prefix.begin(), prefix.end(), a) - prefix.begin(); if(ind <= i && prefix[ind] == a) { mi = min(mi, n - i + ind); } } } if(mi == INT_MAX) return -1; return mi; } };