Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/09/20 22:26)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串415/719 (看更多)

https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/descriptio 1658. Minimum Operations to Reduce X to Zero 給你一個陣列 nums 和一個數字 x ，我們每次可以從陣列的最左或最右拿出一個數字加總並移除該數字，求出最少移除幾個數字後相加會恰好等於 x，如果無法等於 x 返回 -1。思路： 1.元素只能從陣列的左邊和右邊拿，有拿的部分：left + right，其他部分: mid nums = [left][mid][right]。 2.我們需要讓 [left] 和 [right] 相加等於 x 且兩者長度盡可能小，也就是中間部分 [mid] 盡可能大。 3.因為 [left] + [right] = x 且 nums = [left] + [mid] + [right] 所以 [mid] = nums - x，我們可以先用左式把 mid 初始化，如果 [mid] < 0 表示所有元素相加小於 x，可以直接返回。 4.用滑動窗口的技巧不斷加入元素，如果當前窗口的值 > [mid] 就把左邊的元素從窗口 pop，如果窗口的值等於 [mid] 就更新結果值。 (nums 長度減去 [mid] 長度) 5.返回結果。 Java Code： ------------------------------------ class Solution { public int minOperations(int[] nums, int x) { int n = nums.length; int res = Integer.MIN_VALUE; int target = -x; for (int a : nums) { target += a; } if (target < 0) { return -1; } int sum = 0; int j = 0; for (int i = 0; i < n; i++) { sum += nums[i]; while (sum > target) { sum -= nums[j++]; } if (sum == target) { res = Math.max(res, i - j + 1); } } return res == Integer.MIN_VALUE ? -1 : n - res; } } ------------------------------------ -- https://i.imgur.com/DANRJFR.jpg