# 1658. Minimum Operations to Reduce X to Zero
###### tags: `Leetcode` `Medium` `Prefix Sum` `HashMap`
Link: https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/
## 思路
### 思路一 HashMap+PrefixSum $O(N)$ $O(N)$
(2sum 变式)
先从头到尾 用map记录所有prefixsum以及包含它及它的前面有几个item
再从尾到头 算postsum 然后看map里面有没有x-postsum
要注意要保证两次取的item的个数和小于nums.length
### 思路二 Sliding Window $O(N)$ $O(1)$
找到和为totalsum-x的subarray
## Code
### 思路一 HashMap+PrefixSum $O(N)$ $O(N)$

class Solution {
    public int minOperations(int[] nums, int x) {
        Map<Integer, Integer> frontMap = new HashMap<>();
        frontMap.put(0,0);
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        for(int i=0; i<nums.length; i++){
            sum += nums[i];
            frontMap.put(sum, i+1);
        }
        sum = 0;
        for(int i=nums.length; i>=0; i--){
            if(i!=nums.length) sum += nums[i];
            if(frontMap.containsKey(x-sum) && frontMap.get(x-sum)+nums.length-i<=nums.length){
                ans = Math.min(ans, frontMap.get(x-sum)+nums.length-i);
            }
        }
        return ans==Integer.MAX_VALUE?-1:ans;
    }
}

### 思路二 Sliding Window $O(N)$ $O(1)$
java

public class Solution
{
    public int MinOperations(int[] nums, int x)
    {
        int sum = 0;
        for(int num:nums){
            sum += num;
        }
        sum -= x;
        if(sum < 0) return -1;
        if(sum == 0) return nums.length;
        int start = 0, cur = 0, len = -1;
        for(int end = 0; end < nums.length; end++)
        {
            if (cur < sum)
                cur += nums[end];
            while (cur >= sum)
            {
                if (cur == sum)
                    len = Math.Max(len, end - start + 1);
                cur -= nums[start++];
            }
        }

        return len == -1 ? -1 : nums.length - len;
    }
}

c++

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for(int num:nums) sum += num;
        if(sum==x) return nums.size();
        for(int i=1; i<nums.size(); i++){
            nums[i] += nums[i-1];
        }
        map<int, int> map;
        map[0] = -1;
        int maxLen = 0;
        for(int i=0; i<nums.size(); i++){
            if(map.find(nums[i]-(sum-x))!=map.end()){
                maxLen = max(maxLen, i-map[nums[i]-sum+x]);
            }
            if(map.find(nums[i])==map.end()) map[nums[i]] = i;
        }
        if(maxLen==0) return -1;
        return nums.size()-maxLen;
    }
};