Last Updated on 2022-06-11 by Clay
題目
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 is 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 <= 1051 <= nums[i] <= 1041 <= x <= 109
題目的意思很單純，我們有一組陣列，和一個目標值 x。我們只能從該陣列的左邊或右邊開始移除，然後我們要讓移除的值加總正好為 x。當然我們可能會有很多種方法得到跟 x 一樣的移除值，但我們需要找到最少操作的步驟的數量並回傳。
解題思路
滑動窗口（sliding window）
一開始我想要使用 DFS 從左右兩側減去值來遍歷所有可能的答案；但後來發現滑動窗口（sliding window）可能更直觀。
首先我們從左側開始，逐漸將值加總。
如果值正好等於『完整陣列加總值 - x』（也就是目標值），則說明目前並未加進來的值正好就是我們答案的操作步驟。由於我們可能會存在很多不同的操作步驟的解答，所以需要另外一個數值記錄最大的當前加總陣列長度（因為操作步驟最少）。
而一但當前加總值超過了目標值，則我們必須逐步刪除左側值，直到當前加總值小於目標值。
滑動窗口複雜度
| Time complexity | O(n) |
| Space complexity | O(1) |
滑動窗口 C++ 範例程式碼
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
// Init
int target = accumulate(nums.begin(), nums.end(), 0) - x;
int sum = 0;
int max_len = 0;
int left = 0;
bool isFound = false;
// Sliding window
for (int right=0; right<nums.size(); ++right) {
sum += nums[right];
// If the current sum is too large, reduce it.
while (left <= right && sum > target) {
sum -= nums[left];
++left;
}
// Record the maximum length
if (sum == target) {
isFound = true;
max_len = max(max_len, right-left+1);
}
}
return isFound ? nums.size() - max_len : -1;
}
};滑動窗口 Python 範例程式碼
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
# Init
target = sum(nums) - x
_sum = 0
max_len = 0
left = 0
isFound = False
# Sliding window
for right in range(len(nums)):
_sum += nums[right]
# If the current sum is too large, reduce it.
while left <= right and _sum > target:
_sum -= nums[left]
left += 1
# Record the maximum length
if _sum == target:
isFound = True
max_len = max(max_len, right-left+1)
return len(nums)-max_len if isFound else -1