思路1:
前缀和+后缀和。
实现1:
1 class Solution 2 { 3 public: 4 const int INF = 0x3f3f3f3f; 5 int minOperations(vector<int>& nums, int x) 6 { 7 int n = nums.size(), suffix = 0; 8 unordered_map<int, int> mp; 9 mp[0] = n; 10 for (int i = n - 1; i >= 0; i--) 11 { 12 suffix += nums[i]; 13 mp[suffix] = i; 14 } 15 int prefix = 0; 16 int res = INF; 17 if (mp.count(x)) res = n - mp[x]; 18 for (int i = 0; i < n; i++) 19 { 20 mp.erase(suffix); suffix -= nums[i]; 21 prefix += nums[i]; 22 if (mp.count(x - prefix)) 23 { 24 res = min(res, i + 1 + n - mp[x - prefix]); 25 } 26 } 27 return res == INF ? -1: res; 28 } 29 };
思路2:
用滑动窗口在数组中找到和等于sum-x的最长的子段(sum是数组所有元素的和)。
实现2:
class Solution { public: int minOperations(vector<int>& nums, int x) { int n = nums.size(), sum = 0, slow = 0, res = -1; int tot = accumulate(nums.begin(), nums.end(), 0); if (tot == x) return n; x = tot - x; for (int i = 0; i < n; i++) { sum += nums[i]; if (sum >= x) { while (slow <= i and sum >= x) { if (sum == x) res = max(res, i - slow + 1); sum -= nums[slow++]; } } } return res == -1 ? -1: n - res; } };