1658. Minimum Operations to Reduce X to Zero - Medium

前往題目

想法

• Sliding window

思路

這題要反著想，不要湊x，要湊sum(nums) - x -> target

1. 雙指針從左邊開始
2. 每個循環更新當前總和
3. 如果比target大，移動左指針
4. 如果找到和target相等的和，紀錄window大小，找最大的window
5. 最後回傳陣列大小減去最大window就是最少操作數

Code

class Solution {
    public int minOperations(int[] nums, int x) {
        int target = 0;

        // Calculate the target number
        for (int num : nums) {
            target += num;
        }
        target -= x;

        int curSum = 0; // Current sum
        int maxWin = -1; // Max window
        int l = 0;

        for (int r = 0; r < nums.length; ++r) {
            // Update current sum
            curSum += nums[r];

            // Larger than the target
            while (l <= r && curSum > target) {
                curSum -= nums[l];
                ++l;
            }

            // Equals to the target
            if (curSum == target) {
                maxWin = Math.max(maxWin, r - l + 1);
            }
        }

        if (maxWin == -1) return -1;
        return nums.length - maxWin;
    }
}