leetcode 1658. 将 x 减到 0 的最小操作数（优质解法）

代码：

class Solution {
    public int minOperations(int[] nums, int x) {
        int sum=0;  // nums 数组中的数据总和
        int length=nums.length;
        for(int i=0;i<length;i++){
            sum+=nums[i];
        }

        int target=sum-x;   //待查找的子数组的和
        if(target<0){
            return -1;
        }

        //采用滑动窗口的方法查找合适的子数组
        int maxLrngth=-1;   //记录子数组的最大长度
        int sonSum=0;   //记录当前讨论的子数组的和
        for (int left=0,right=0;right<length;right++){
            sonSum+=nums[right];
            while (sonSum>target){
                sonSum-=nums[left++];
            }
            if(sonSum==target){
                //此时 left 和 right 指针之间的子数组符合条件
                //记录当前子数组的长度
                maxLrngth=Math.max(maxLrngth,right-left+1);
            }
            //sonSum < target
        }

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

        return nums.length-maxLrngth;
    }
}

题解：

? ? ? ? 我们直接分析题意的话会发现这个题目还是很复杂的，因为我们不能确定当前是要让 x 减去左边的值还是右边的值，也不能确定当前的选择是否是最佳的选择，当我们觉得题目当前问的问题很复杂时，我们不妨换个方向来看这个问题

? ? ? ? 我们要移除最左边或者最右边的元素，让 x 的值减为 0 ，就相当于，我们要选取最左边或最右边的值，让选取的值相加为 x ，由于我们只从最左或最右边开始选取，这就代表，选取值以后，剩下没有被选取的值是连续的，说明是原数组的一个子数组

? ? ? ? 于是我们可以这样看题，现在需要我们从该数组中找到一个子数组，让子数组的和?target = sum（数组的总和）- x ，并且子数组的长度要最长（因为操作数要最小）

? ? ? ? 这样的话题目就简单很多了，对于讨论子数组的题，我们通常可以采用滑动窗口的方式解决，现在思考一下暴力解法：我们找到数组中所有的子数组，筛选出和为 target 的子数组，最后选择最长的子数组便得到了结果

? ? ? ? 以示例1作为例子，输入：nums = [1,1,4,2,3], x = 5，target = 11-5 = 6我们让指针 L 和 R 指向下标 0 ，L 和 R 指针之间的数据便是我们要讨论的子数组，当 子数组的和小于 target 时，我们让 R ++ ，扩大我们讨论的子数组

1? ? ? ? 1? ? ? ? 4? ? ? ? 2? ? ? ? 3

L

R

? ? ? ? 当 R 指针指到当前位置时，我们讨论的子数组的和为 6 == target ，所以此时的子数组是符合条件的，我们将子数组的长度进行保存（与之前保存的长度进行比较，取较大的保存），此时以 L 指针为首位的子数组已经讨论完毕，我们让 L++

1? ? ? ? 1? ? ? ? 4? ? ? ? 2? ? ? ? 3

L

? ? ? ? ? ? ? ? ? ? R? ?

? ? ? ? 现在就涉及到一个问题，我们需要让 R 指针回到 L 指针所在的位置，从头开始讨论子数组吗？答案是：不需要，因为 R 指针在上一轮中到达当前的位置就代表，?R 指针左边的数据之和是小于 target 的，即使 R 指针回到 L 指针所在的位置，也会回到当前的位置，所以没有必要回去

? ? ? ? 我们直接判断当前子数组的和，此时和为 5 < target ,

1? ? ? ? 1? ? ? ? 4? ? ? ? 2? ? ? ? 3

? ? ? ? ? ?L? ? ?

? ? ? ? ? ? ? ? ? ? R?

????????于是我们让 R ++ ，扩大我们讨论的子数组,此时子数组的和为 7 > target，代表以 L 指针为首位的子数组已经讨论完毕

1? ? ? ? 1? ? ? ? 4? ? ? ? 2? ? ? ? 3

? ? ? ? ? ?L? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? R?

????????于是我们让 L++,接下来就是循环上面提到的操作了

1? ? ? ? 1? ? ? ? 4? ? ? ? 2? ? ? ? 3

? ? ? ? ? ? ? ? ? ? L? ? ??? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? R?

? ? ? ? 当 R 指针移动到 nums.length 的位置时，循环结束，讨论完毕

1? ? ? ? 1? ? ? ? 4? ? ? ? 2? ? ? ? 3

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? L? ? ??? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????R?