1658.md

【中规中矩】1658. 将 x 减到 0 的最小操作数

解题思路

此题精妙之处在于如何把未知未见过的问题转换为已知见过的问题。其实如果求是否存在两边的数和为x，等价于求是否有连续区间的总和等于sum - x（假设sum为所有元素的总和）。如果存在这样的区间，那么其两边的元素和必然为x。如果存在多个这样的区间，取最长的那个区间len，则N-len就是我们要求的最少删除元素个数令x减少为0.

注意一个坑：如果sum < x 则target可以为负数，因此要判断i < N 防止越界。否则测试用例[1, 1] x = 3 fail.

代码

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        assert(!nums.empty());
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int target = sum - x;
        int windowSum = 0;
        int N = nums.size();
        int maxLen = -1;
        for (int i = 0, j = 0; j < nums.size(); j++) {
            windowSum += nums[j];
            while (i < N && windowSum > target) { // 坑，别忘i < N
                windowSum -= nums[i];
                i++;
            }

            if (windowSum == target) {
                maxLen = max(maxLen, j - i + 1);
            }
        }

        if (maxLen == -1) {
            return -1;
        }

        return N - maxLen;
    }
};

import numpy
class Solution(object):
    def minOperations(self, nums, x):
        sum = numpy.sum(nums)
        target = sum - x
        windowSum = 0
        N = len(nums)
        maxLen = -1
        i = 0
        for j in range(0, len(nums)) :
            windowSum += nums[j]
            while (i < N and windowSum > target) : # 坑，别忘i < N
                windowSum -= nums[i]
                i += 1
            

            if (windowSum == target) :
                maxLen = max(maxLen, j - i + 1)
            
        

        if (maxLen == -1) :
            return -1
        

        return N - maxLen

Update 2021/03/21: 新增python解法。

点我赞赏作者

github 题解