Leetcode 1658. Minimum Operations to Reduce X to Zero

문제

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.

정수 배열 nums와 정수 x가 주어집니다.
한 Operation 을 통해 nums의 왼쪽 끝이나 오른쪽 끝의 값을 제거하고 그만큼의 값을 x로부터 제거할수 있습니다.
최소한의 Operation 을 통해 x를 0으로 만들수 있는 Operation 의 횟수를 구하시오
단, 불가능할 경우엔 -1을 리턴합니다.

예시

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: 최적의 경우는 오른쪽에서 두번 제거한다.

제한

• $1 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^4$
• $1 <= x <= 10^9$

풀이

• 왼쪽과 오른쪽의 부분배열을 따로 구한다고 생각하기 쉬운데 포인트는 다르다.
• 전체합 - 찾아야할 숫자에 주목해보자, 이 결과는 전체 배열에서 왼쪽 부분배열과 오른쪽 부분배열을 제거한 부분배열의 합이 될것이다.
• 즉, 이 중간에 위치한 부분배열의 길이가 최대한 길어진다면? 양 옆의 부분배열의 길이는 자연스럽게 최소가 된다.
• 이를 구하기 위해 Sliding window 기법을 사용한다.

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        if sum(nums) - x == 0:
            return len(nums)
        if sum(nums) < x:
            return -1

        target = sum(nums) - x
        
        left = maximum = acc = count = 0
        
        for right, value in enumerate(nums):
            acc += nums[right]
            # 만약 값이 너무 크다면, 왼쪽부터 Sliding window의 크기를 줄인다.
            while left < right and target < acc:
                acc -= nums[left]
                left += 1
            if target == acc:
                maximum = max(maximum, right - left + 1)
         # maximum의 값이 0이라는것은 하나도 구하지 못했다는 뜻이기에 그냥 -1을 리턴하면 된다.
        return len(nums) - maximum if maximum != 0 else -1