14일 - X를 0으로 줄이기 위한 최소 작업

문제

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.

예 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.

예 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

예 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.

제약:

1 <= nums.length <= 105

1 <= nums[i] <= 104

1 <= x <= 109

내 테스트

Link to code

import pytest
from .Day14_MinimumOperationsToReduceXToZero import Solution

s = Solution()


@pytest.mark.parametrize(
    "nums,x,expected",
    [([1, 1, 4, 2, 3], 5, 2), ([5, 6, 7, 8, 9], 4, -1), ([3, 2, 20, 1, 1, 3], 10, 5)],
)
def test_min_operations(nums, x, expected):
    assert s.minOperations(nums, x) == expected

내 솔루션

Link to code

from typing import List


class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        total = sum(nums)
        remainder = total - x
        n = len(nums)
        largest_subarray_len = -1
        current_sum = 0

        j = 0
        for i in range(n):
            current_sum += nums[i]
            while current_sum > remainder and j <= i:
                current_sum -= nums[j]
                j += 1
            if current_sum == remainder:
                largest_subarray_len = max(largest_subarray_len, i - j + 1)

        if largest_subarray_len == -1:
            return largest_subarray_len

        return n - largest_subarray_len

분석

내 해설

내가 사용하게 된 문제에는 2개의 힌트가 있었습니다.

Think in reverse; instead of finding the minimum prefix + suffix, find the maximum subarray.

Finding the maximum subarray is standard and can be done greedily.

The Max Sub Array Problem은 상당히 간단하게 해결할 수 있습니다. 내가 처음에 까다롭다고 생각한 부분은 정확히 어떤 최대 하위 배열을 찾아야 하는지 파악하는 것이었습니다. 나는 어레이의 전처리를 피하려고 노력했지만 거기에서 좋은 것을 얻을 수 없었습니다. 항상 전체 배열을 살펴보지 않고 하위 배열을 찾는 것은 너무 어려운 것 같습니다. 좋은 해결책은 (힌트가 말했듯이) 역으로 생각하고 sum(nums) - x 인 가장 큰 하위 배열을 찾는 것입니다. 해당 하위 배열의 길이를 알고 있는 경우 길이nums에서 길이를 빼서 작업 수를 얻을 수 있습니다.



처음에 배열을 합산하더라도 솔루션은 여전히 ​​O(n) 그리 나쁘지 않습니다.