将x减到0的最小操作数

给你一个整数数组 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

示例 3：
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

$1 <= nums.length <= 10^5$

$1 <= nums[i] <= 10^4$

$1 <= x <= 10^9$

前缀和+哈希表

1. 分别计算从前往后和从后往前的前缀和
2. 使用哈希表保存前缀和的值与index（用来降低时间复杂度）

• 因为每次都从数组的第一个和最后一个元素取，并且取完后删除那个元素，所以说每次取都是连续的从前往后取或者是连续的从后往前取，也就是从前往后的前缀和和从后往前的前缀和，因此使用前缀和可以降低时间复杂度。
• 为了求最小值，要使用两层循环分别计算从前往后的前缀和prefix[i]与从后往前的前缀和suffix[j]的和，判断其是否等于x,如果等于x，那么更新i+j的最小值。但是这样计算出现了超时，为了降低时间复杂度，因为 $1 <= nums[i] <= 10^4$ ，所以前缀和是递增的，不会有重复值，我们可以使用哈希表来去掉一层循环，哈希表的键为前缀和，哈希表的值为index，当map.containsKey(x-prefix[i])时，即满足条件更新min=Math.min(i+map.get(x-prefix[i]),min)

class Solution {
    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];

        // 降低时间复杂度的哈希表
        Map<Integer, Integer> map1 = new HashMap<>();
        Map<Integer, Integer> map2 = new HashMap<>();
        map1.put(0, 0);
        map2.put(0, 0);

        // 计算前缀和
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
            suffix[i] = suffix[i - 1] + nums[n - i];
            map1.put(prefix[i], i);
            map2.put(suffix[i], i);
        }

        int min = n + 1;
        for (int i = 0; i <= n; i++) {
            int val = prefix[i];
            if (val > x) break;

            int subtract = x - val;
            if (map2.containsKey(subtract)) {
                min = Math.min(min, i + map2.get(subtract));
            }
        }
        for (int i = 0; i <= n; i++) {
            int val = suffix[i];
            if (val > x) break;

            int subtract = x - val;
            if (map1.containsKey(subtract)) {
                min = Math.min(min, i + map1.get(subtract));
            }
        }
        return min == n + 1 ? -1 : min;
    }
}

时间复杂度$O(n)$,空间复杂度$O(n)$

赏

谢谢你请我吃糖果

微信