LeetCode 1658. 将 x 减到 0 的最小操作数

Categories:

题目描述
思路分析
1. 解法一：转化为最长子数组（推荐）
相似题目

题目描述

✅ 1658. 将 x 减到 0 的最小操作数

思路分析

解法一：转化为最长子数组（推荐）

核心思路：

移除两端等价于保留中间子数组。

设数组总和为 sum，目标是找到和为 sum - x 的最长子数组。

用滑动窗口在正整数数组中求最长符合区间。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int minOperations(int[] nums, int x) {
        int total = 0;
        for (int v : nums) {
            total += v;
        }

        int target = total - x;
        if (target < 0) {
            return -1;
        }
        if (target == 0) {
            return nums.length;
        }

        int left = 0;
        int sum = 0;
        int maxLen = -1;

        // 滑动窗口寻找最长子数组
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum > target && left <= right) {
                sum -= nums[left++];
            }
            if (sum == target) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }

        return maxLen == -1 ? -1 : nums.length - maxLen;
    }
}

func minOperations(nums []int, x int) int {
	total := 0
	for _, v := range nums {
		total += v
	}

	target := total - x
	if target < 0 {
		return -1
	}
	if target == 0 {
		return len(nums)
	}

	left := 0
	sum := 0
	maxLen := -1

	// 滑动窗口寻找最长子数组
	for right := 0; right < len(nums); right++ {
		sum += nums[right]
		for sum > target && left <= right {
			sum -= nums[left]
			left++
		}
		if sum == target {
			if right-left+1 > maxLen {
				maxLen = right - left + 1
			}
		}
	}

	if maxLen == -1 {
		return -1
	}
	return len(nums) - maxLen
}

相似题目

题目	难度	考察点
209. 长度最小的子数组	中等	滑动窗口
560. 和为 K 的子数组	中等	前缀和
930. 和相同的二元子数组	中等	双指针
1248. 统计优美子数组	中等	前缀和
152. 乘积最大子数组	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/33372018