滑動窗口應用題 Minimum Operations to Reduce X to Zero_Leetcode #165

這題題目在這裡:

題目會給定我們一個陣列，還有一個整數值x

測試範例:

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.
取最尾巴的3和2​

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.
取頭部的3, 2
取尾巴的1, 1, 3
最後取出的數字總和為10​

演算法:

維護一個滑窗，令滑窗的目標值為 sum( nums ) - x = 陣列總和 - x

則 藍色部分(滑窗內的元素和) + 綠色部分(題目原本所求)
= (陣列總和 - x) + x
= 陣列總和 = sum(nums)

題目所求為 湊到x的最小次數，相當於

Sliding window 內總和為 sum( nums ) - x ，伴隨著最大的滑窗長度。

最後， 湊到x的最小次數 = len(nums) - 最大的滑窗長度

程式碼:

class Solution:
　def minOperations(self, nums: List[int], x: int) -> int:
　　
　　# Min operation to meet x
　　# <=> Max operation to meet sum(nums) - x
　　target = sum(nums) - x

　　if target < 0:
　　　# Quick response for no solution
　　　return -1

　　# left boundary of sliding window
　　left = 0

　　# summation of sliding window
　　summation = 0

　　# max length of sliding window whose sum is equal to ( sum(nums) - x )
　　max_len = -1

　　# Use sliding window to maximize window length, whose sum is equal to ( sum(nums) - x )
　　for right, val in enumerate( nums ):
　　　
　　　summation += val

　　　while summation > target:
　　　　summation -= nums[left]
　　　　left += 1

　　　if summation == target:
　　　　cur_len = right - left + 1
　　　　max_len = max(max_len, cur_len)

　　# We cannot find interval sum = ( sum(nums) - x ), so no solution
　　if max_len == -1:
　　　return max_len

　　# Min operation to meet x
　　# <=> Max operation to meet sum(nums) - x　　
　　return len(nums) - max_len

時間複雜度:

O( n ) 成本耗費在滑動窗口 sliding window的拓展

空間複雜度:

O( 1 ) 使用到的都是臨時變數，占用記憶體空間是固定常數級別O( 1 )

Reference:

[1] Minimum Operations to Reduce X to Zero — LeetCode