1658.将x减到0的最小操作数

链接：1658.将x减到0的最小操作数
难度：Medium
标签：数组、哈希表、二分查找、前缀和、滑动窗口
简介：给你一个整数数组 nums 和一个整数 x 。如果可以将 x 恰好 减到 0 ，返回 最小操作数 。

题解 1 - typescript

• 编辑时间：2021-07-22
• 执行用时：192ms
• 内存消耗：60.9MB
• 编程语言：typescript
• 解法介绍：前缀和。

function minOperations(nums: number[], x: number): number {
  const sumsL = [0];
  const sumsR = [0];
  const n = nums.length;
  for (let i = 0; i < n; i++) sumsL.push(nums[i] + sumsL[i]);
  for (let i = 0; i < n; i++) sumsR.push(nums[n - 1 - i] + sumsR[i]);
  let ans = Infinity;
  for (let i = 0; i <= n; i++) {
    const num = sumsL[i];
    const need = x - num;
    if (need < 0) break;
    let l = 0;
    let r = sumsR.length - 1;
    let mid!: number;
    while (l <= r) {
      mid = (l + r) >> 1;
      const midNum = sumsR[mid];
      if (midNum < need) l = mid + 1;
      else if (midNum > need) r = mid - 1;
      else break;
    }
    if (need === sumsR[mid] && i + mid <= n) {
      ans = Math.min(ans, i + mid);
    }
  }
  return ans === Infinity ? -1 : ans;
}

题解 2 - cpp

• 编辑时间：2023-01-07
• 执行用时：404ms
• 内存消耗：164.3MB
• 编程语言：cpp
• 解法介绍：哈希存储。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        unordered_map<int, int> lmap;
        lmap[0] = 0;
        int ans = 0x7fffffff, n = nums.size();
        for (int i = 0, sum = 0; i < n; i++) {
            sum += nums[i];
            if (sum == x) ans = min(ans, i + 1);
            if (!lmap.count(sum)) lmap[sum] = i + 1;
        }
        for (int i = n - 1, sum = 0; i >= 0; i--) {
            sum += nums[i];
            if (sum > x) break;
            if (!lmap.count(x - sum)) continue;
            if (lmap[x - sum] + n - i > n) continue;
            ans = min(ans, lmap[x - sum] + n - i);
        }
        return ans == 0x7fffffff ? -1 : ans;
    }
};

题解 3 - cpp

• 编辑时间：2023-01-07
• 执行用时：128ms
• 内存消耗：96.3MB
• 编程语言：cpp
• 解法介绍：滑动窗口。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int ans = 0x7fffffff, n = nums.size(), r = 0, rsum = accumulate(nums.begin(), nums.end(), 0);
        if (rsum < x) return -1;
        while (r < n && rsum > x) rsum -= nums[r++];
        if (rsum == x) ans = n - r;
        for (int l = 0, lsum = 0; l < n; l++) {
            lsum += nums[l];
            while (r < n && (l + 1 + n - r > n || lsum + rsum > x)) rsum -= nums[r++];
            if (lsum + rsum == x) ans = min(ans, l + 1 + n - r);
        }
        return ans == 0x7fffffff ? -1 : ans;
    }
};

题解 4 - rust

• 编辑时间：2023-01-07
• 执行用时：20ms
• 内存消耗：2.8MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_operations(nums: Vec<i32>, x: i32) -> i32 {
        let mut ans = i32::MAX;
        let n = nums.len();
        let (mut r, mut rsum) = (0, nums.iter().fold(0, |sum, cur| sum + cur));
        if rsum < x {
            return -1;
        }
        while r < n && rsum > x {
            rsum -= nums[r];
            r += 1;
        }
        if rsum == x {
            ans = (n - r) as i32;
        }
        let (mut l, mut lsum) = (0, 0);
        while l < n {
            lsum += nums[l];
            while r < n && (l + 1 + n - r > n || lsum + rsum > x) {
                rsum -= nums[r];
                r += 1;
            }
            if lsum + rsum == x {
                ans = ans.min((l + 1 + n - r) as i32);
            }
            l += 1;
        }
        if ans == i32::MAX {
            -1
        } else {
            ans
        }
    }
}