You are given an integer array nums
and an integer x
. In one operation, you can either remove the leftmost or the rightmost element from the array nums
and subtract its value from x
. Note that this modifies the array for future operations.
Return the minimum number of operations to reduce x
to exactly 0
if it’s possible, otherwise, return -1
.
Example 1:
Input: nums = [1,1,4,2,3], x = 5 Output: 2 Explanation: The optimal solution is to remove the last two elements to reduce x to zero.
Example 2:
Input: nums = [5,6,7,8,9], x = 4 Output: -1
Example 3:
Input: nums = [3,2,20,1,1,3], x = 10 Output: 5 Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109
Solution1: Prefix Sum + Hashtable
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: int minOperations(vector<int>& nums, int x) { const int n = nums.size(); vector<int> l(n), r(n); unordered_map<int, int> ml, mr; ml[0] = mr[0] = -1; for (int i = 0; i < n; ++i) { l[i] = nums[i] + (i > 0 ? l[i - 1] : 0); r[i] = nums[n - i - 1] + (i > 0 ? r[i - 1]: 0); ml[l[i]] = mr[r[i]] = i; } int ans = INT_MAX; for (int i = 0; i < n; ++i) { int s1 = x - l[i]; auto it1 = mr.find(s1); if (it1 != mr.end()) ans = min(ans, i + 1 + it1->second + 1); int s2 = x - r[i]; auto it2 = ml.find(s2); if (it2 != ml.end()) ans = min(ans, i + 1 + it2->second + 1); } return ans > n ? -1 : ans; } }; |
Solution2: Sliding Window
Find the longest sliding window whose sum of elements equals sum(nums) – x
ans = n – window_size
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int minOperations(vector<int>& nums, int x) { const int n = nums.size(); int target = accumulate(begin(nums), end(nums), 0) - x; int ans = INT_MAX; for (int s = 0, l = 0, r = 0; r < n; ++r) { s += nums[r]; while (s > target && l <= r) s -= nums[l++]; if (s == target) ans = min(ans, n - (r - l + 1)); } return ans > n ? -1 : ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment