[leetcode每日一题]1.7

​​1658. 将 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 <= 105​​
• ​​1 <= nums[i] <= 104​​
• ​​1 <= x <= 109​​

Solution

我想到的方法是之前周赛的某一个解法，将需要移除的后缀和用哈希表存储，再遍历前缀和进行匹配。

代码(Rust)

impl Solution {
    pub fn min_operations(nums: Vec<i32>, x: i32) -> i32 {
        use std::collections::HashMap;
        let mut right: HashMap<i32, i32> = HashMap::new();
        let n = (nums.len()) as i32;
        right.insert(0, n);
        let mut cur = 0;
        for i in (0..n as usize).rev() {
            cur += nums[i];
            right.insert(cur, i as i32);
        }
        if cur == x {
            return n as i32;
        }
        else if cur < x {
            return -1;
        }
        let mut min_ = n + 1;
        let mut tmp = 0;
        if let Some(val) = right.get(&x) {
            min_ = if min_ > n - *val {
                    n - *val
            } else {
                min_
            };
        }
        for i in 0..n as usize {
            tmp += nums[i]; 
            if let Some(val) = right.get(&(x - tmp as i32)) {
                min_ = if min_ > n - *val + i as i32 + 1 {
                    n - *val + i as i32 + 1
                } else {
                    min_
                };
            }
        }
        if min_ == n + 1 {
            return -1;
        }
        min_
    }
}

但是官方题解用了一个性能更好的滑动窗口来解。学到了。