12.将 x 减到 0 的最小操作数 | 滑动窗口+正难则反

目录1. 题目解析2. 算法原理2.1 正难则反的转换2.2 滑动窗口解法3. 编写代码4. 总结1. 题目解析题目1658. 将 x 减到 0 的最小操作数链接1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode题意给你一个整数数组nums和一个整数x每一次操作时你应当移除数组nums最左边或最右边的元素然后从x中减去该元素的值。请注意需要修改数组以供接下来的操作使用。如果可以将x恰好减到 0返回最小操作数否则返回 -1。示例 1输入nums [1,1,4,2,3], x 5输出2解释最佳解决方案是移除后两个元素将 x 减到 0。示例 2输入nums [5,6,7,8,9], x 4输出-1注释从数组两端移除元素x 的变化过程比如示例 1 中移除最后两个元素[2,3]x 从 5→3→0共 2 次另一种尝试移除前两个[1,1]x 5→4→3不是最优。2. 算法原理核心思路正难则反 滑动窗口​2.1 正难则反的转换我们需要让x减到 0相当于从数组的两端移除元素使这些元素的和等于x。反过来想如果我们能找到一个中间子数组其和为sum - xsum是数组总和那么剩下的元素两端的就是需要移除的且移除的数量最少。设数组总和为sum目标子数组的和为target sum - x。我们需要找到最长的子数组其和等于target。这样移除的元素数量操作数就是n - lenn是数组长度len是子数组长度。数组整体和为sum中间子数组和为target sum - x则两端移除的元素和为x。要最小化操作数即最大化中间子数组的长度len操作数为n - len。2.2 滑动窗口解法滑动窗口用于找最长子数组和为 target​ 的情况步骤如下初始化left 0, right 0窗口左右边界tmp 0窗口内元素和。右边界right右移进窗口tmp nums[right]。若tmp target则左边界left右移出窗口tmp - nums[left]直到tmp target。若tmp target更新最大长度ret Math.max(ret, right - left 1)。3. 编写代码class Solution { public int minOperations(int[] nums, int x) { int sum 0; for (int a : nums) sum a; int target sum - x; // 处理细节如果target小于0说明无法通过移除两端元素让x到0 if (target 0) return -1; int ret -1; for (int left 0, right 0, tmp 0; right nums.length; right) { tmp nums[right]; // 进窗口 while (tmp target) { // 判断窗口和超过target需要缩小窗口 tmp - nums[left]; // 出窗口 } if (tmp target) { ret Math.max(ret, right - left 1); // 更新最长子数组长度 } } if (ret -1) return ret; // 没找到符合条件的子数组 else return nums.length - ret; // 操作数 总长度 - 最长子数组长度 } }4. 总结这道题的关键是转换思路将“两端移除元素使和为 x”转化为“中间子数组和为 sum - x”再用滑动窗口找最长子数组。需要注意处理target 0的边界情况以及最终操作数的计算n - ret。这道题最阴险的就是他需要你维护的滑动窗口是需要你画图转换得出的其实比之前的题来说就多了一步转换罢了~