【Day 47 】2023-04-01 - Number of Operations to Decrement Target to Zero

[azl397985856]

Number of Operations to Decrement Target to Zero

入选理由

暂无

题目地址

https://binarysearch.com/problems/Number-of-Operations-to-Decrement-Target-to-Zero

前置知识

暂无

题目描述

You are given a list of positive integers nums and an integer target. Consider an operation where we remove a number v from either the front or the back of nums and decrement target by v.

Return the minimum number of operations required to decrement target to zero. If it's not possible, return -1.

Constraints

n ≤ 100,000 where n is the length of nums Example 1 Input nums = [3, 1, 1, 2, 5, 1, 1] target = 7 Output 3 Explanation We can remove 1, 1 and 5 from the back to decrement target to zero.

Example 2 Input nums = [2, 4] target = 7 Output -1 Explanation There's no way to decrement target = 7 to zero.

[JasonQiu]

• Two pointers

  def removeFromSides(nums, target):
  result = math.inf
  left = len(nums) - 1
  right = len(nums)
  target -= sum(nums)
  
  while left >= 0:
      if target <= 0:
          target += nums[left]
          left -= 1
      if target > 0:
          right -= 1
          target -= nums[right]
      if target == 0:
          result = min(result, left + 1 + len(nums) - right)
  
  return result if result < math.inf else -1

  Time: O(n) Space: O(1)

[LIMBO42]

滑动窗口题，只需要使得中间连续出现和为sum-k的窗口即可

[Meisgithub]

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        unordered_map<int, int> mp;
        mp[0] = -1;
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            sum += nums[i];
            mp[sum] = i;
        }
        if (sum == x)
        {
            return n;
        }
        int ans = 0x3f3f3f3f3f;
        int total = sum;
        sum = 0;
        if (mp.count(total - x + sum))
        {
            // cout << total - x + sum << endl;
            ans = min(ans, -1 + n - mp[total - x + sum]);
        }
        for (int i = 0; i < n; ++i)
        {
            sum += nums[i];
            if (mp.count(total - x + sum))
            {
                // cout << total - x + sum << endl;
                if (mp[total - x + sum] >= i)
                {
                    ans = min(ans, i + n - mp[total - x + sum]);
                }
            }
        }
        return ans == 0x3f3f3f3f ? -1 : ans;
    }
};

[aoxiangw]

def solve(A, target):
    if not A and not target:
        return 0
    newT = sum(A) - target
    ans = len(A) + 1
    i = t = 0

    for j in range(len(A)):
        t += A[j]
        while i <= j and t > newT:
            t -= A[i]
            i += 1
        if t == newT:
            ans = min(ans, len(A) - (j - i + 1))
    return -1 if ans == len(A) + 1 else ans

time, space: O(n), O(1)

[bookyue]

TC: O(n)
SC: O(1)

    public int maxScore(int[] cardPoints, int k) {
        int w = cardPoints.length - k;

        int sumW = 0;
        for (int i = 0; i < w; i++) 
            sumW += cardPoints[i];

        int ans = sumW;
        int sum = sumW;
        for (int i = w; i < cardPoints.length; i++) {
            sumW -= cardPoints[i - w];
            sumW += cardPoints[i];
            sum += cardPoints[i];

            ans = Math.min(ans, sumW);
        }

        return sum - ans;
    }

[Abby-xu]

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n = len(nums)

        leftMap = dict()
        leftMap[0] = -1
        left = 0
        for i in range(n):
            left += nums[i]
            if left not in leftMap:
                leftMap[left] = i

        right = 0
        ans = n + 1
        for i in range(n, -1, -1):
            if i < n:  right += nums[i]
            left = x - right
            if left in leftMap:  # left + right = x -> left = x - right
                ans = min(ans, leftMap[left] + 1 + n - i)
        if ans == n + 1: return -1
        return ans

[FireHaoSky]

思路：滑动窗口+前缀和

代码：python

def min_operations(nums, target):
    # 计算 nums 的前缀和数组 prefix
    prefix = [0] * (len(nums) + 1)
    for i in range(len(nums)):
        prefix[i+1] = prefix[i] + nums[i]
    # 初始化左右指针和删除元素的次数
    left, right, cnt = 0, 0, float('inf')
    while right < len(nums):
        # 如果当前滑动窗口中的元素之和小于等于 target，则将右指针向右移动
        if prefix[right+1] - prefix[left] <= target:
            right += 1
        else:
            # 如果当前滑动窗口中的元素之和大于 target，则将左指针向右移动
            left += 1
        # 如果当前滑动窗口中的元素之和等于 target，则更新删除元素的次数
        if prefix[right] - prefix[left] == target:
            cnt = min(cnt, right - left)
    # 如果没有找到任何一个满足条件的滑动窗口，则返回 -1
    if cnt == float('inf'):
        return -1
    else:
        return cnt

复杂度分析：

时间复杂度：O(n) 空间复杂的：O(1)

[wangqianqian202301]

class Solution(object):
    def minOperations(self, nums, x):
        target = sum(nums) - x

        if target == 0:
            return len(nums)

        left, right = 0, 0 
        curr, cnt = 0, 0 

        while right < len(nums):
            curr = curr + nums[right]

            while left < right and curr > target:
                curr = curr - nums[left]
                left = left + 1
            if curr == target:
                cnt = max(cnt, right - left + 1)
            right = right + 1

        if cnt == 0:
            return -1 
        else:
            return len(nums) - cnt 

[Fuku-L]

代码

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int windowSize = n - k;
        int sum = 0;
        for(int i = 0; i< windowSize; i++){
            sum += cardPoints[i];
        }
        int minSum = sum;
        for(int i = windowSize; i<n; i++){
            sum += cardPoints[i] - cardPoints[i - windowSize];
            minSum = minSum < sum ? minSum : sum; 
        }
        return Arrays.stream(cardPoints).sum() - minSum;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[wangzh0114]

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int newTarget = 0;
        int sum = 0;
        for(auto e:nums){
            sum += e;
        }
        newTarget = sum - x;
        if(newTarget == 0)return nums.size();
        int left = 0;
        int tempSum = 0;
        int maxlen = 0;
        for(int i=left; i<nums.size(); i++){
            tempSum += nums[i];
            while(tempSum >= newTarget && i>=left){
                if(tempSum == newTarget){
                    maxlen = max(maxlen, i-left+1);
                }
                tempSum -= nums[left];
                left++;
            }

        }
        return maxlen == 0 ? -1 : nums.size() - maxlen;
    }
};

• TC:O(N)
• SC:O(1)

[harperz24]

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        totalSum = sum(cardPoints)
        windowSum = sum(cardPoints[:n - k])
        maxPoints = totalSum - windowSum

        for i in range(k):
            windowSum += cardPoints[n - k + i] - cardPoints[i]
            maxPoints = max(maxPoints, totalSum - windowSum)

        return maxPoints

        # sliding window
        # time: O(n)
        # space: O(1)

[Hughlin07]

class Solution {

public int maxScore(int[] cardPoints, int k) {

    int blockSize = cardPoints.length - k;
    int sum = 0;
    for(int i = 0; i< blockSize; i++){
        sum += cardPoints[i];
    }

    int minSum = sum;
    for(int i = blockSize; i < n; i++){
        sum += cardPoints[i] - cardPoints[i - blockSize];
        minSum = minSum < sum ? minSum : sum; 
    }

    return Arrays.stream(cardPoints).sum() - minSum;
}

}

[joemonkeylee]

思路

滑动窗口

代码

     public int MinOperations(int[] nums, int x)
        {
            int total = 0;
            int length = nums.Length;
            for (int i = 0; i < length; i++)
            {
                total += nums[i];
            }
            int remain = total - x;
            if (remain == 0)
            {
                return length;
            }
            else if (remain < 0)
            {
                return -1;
            }
            int maxLength = -1;
            int sum = 0;
            int start = 0, end = 0;
            while (end < length)
            {
                sum += nums[end];
                while (sum > remain)
                {
                    sum -= nums[start];
                    start++;
                }
                if (sum == remain)
                {
                    maxLength = Math.Max(maxLength, end - start + 1);
                }
                end++;
            }
            return maxLength < 0 ? -1 : length - maxLength;
        }

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[kangliqi1]

public int maxScore(int[] cardPoints, int k) {

int blockSize = cardPoints.length - k;
int sum = 0;
for(int i = 0; i< blockSize; i++){
    sum += cardPoints[i];
}

int minSum = sum;
for(int i = blockSize; i < n; i++){
    sum += cardPoints[i] - cardPoints[i - blockSize];
    minSum = minSum < sum ? minSum : sum; 
}

return Arrays.stream(cardPoints).sum() - minSum;

}

[enrilwang]

public int maxScore(int[] cardPoints, int k) { int w = cardPoints.length - k;

    int sumW = 0;
    for (int i = 0; i < w; i++) 
        sumW += cardPoints[i];

    int ans = sumW;
    int sum = sumW; public int maxScore(int[] cardPoints, int k) {
    int w = cardPoints.length - k;

    int sumW = 0;
    for (int i = 0; i < w; i++) 
        sumW += cardPoints[i];

    int ans = sumW;
    int sum = sumW;
    for (int i = w; i < cardPoints.length; i++) {
        sumW -= cardPoints[i - w];
        sumW += cardPoints[i];
        sum += cardPoints[i];

        ans = Math.min(ans, sumW);
    }

    return sum - ans;
}
    for (int i = w; i < cardPoints.length; i++) {
        sumW -= cardPoints[i - w];
        sumW += cardPoints[i];
        sum += cardPoints[i];

        ans = Math.min(ans, sumW);
    }

    return sum - ans;
}

[lp1506947671]

class Solution:
    def solve(self, A, target):
        if not A and not target: return 0
        target = sum(A) - target
        ans = len(A) + 1
        i = t = 0

        for j in range(len(A)):
            t += A[j]
            while i <= j and t > target:
                t -= A[i]
                i += 1
            if t == target: ans = min(ans, len(A) - (j - i + 1))
        return -1 if ans == len(A) + 1 else ans

复杂度分析

令 n 为数组长度。

• 时间复杂度：O(n
• 空间复杂度：1

[RestlessBreeze]

code

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        totalSum = sum(cardPoints)
        Sum = sum(cardPoints[:n - k])
        maxPoints = totalSum - Sum

        for i in range(k):
            Sum += cardPoints[n - k + i] - cardPoints[i]
            maxPoints = max(maxPoints, totalSum - Sum)

        return maxPoints

[Lydia61]

Number of Operation to Decrement Target to Zero

思路

1、蠢方法：动态规划 2、好方法：滑动窗口

代码

int solve(vector<int>& nums, int target) {
    int N = nums.size();
    int newTarget = accumulate(nums.begin(), nums.end(), 0) - target;
    if (newTarget == 0) return N;
    int curSum = 0;
    int maxLen = 0;
    int left = 0; 
    for (int i = 0; i < N; i++)
    {
        curSum += nums[i];
        while (curSum >= newTarget && i >= left)
        {
            if (curSum == newTarget) 
                maxLen = max(maxLen, i - left + 1);

            curSum -= nums[left]; 
            left++;
        }
    }
    return maxLen == 0 ? -1 : N - maxLen;

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[AstrKing]

代码

public int MinOperations(int[] nums, int x){
    int total = 0;
    int length = nums.Length;
    for (int i = 0; i < length; i++)
    {
        total += nums[i];
    }
    int remain = total - x;
    if (remain == 0)
    {
        return length;
    }
    else if (remain < 0)
    {
        return -1;
    }
    int maxLength = -1;
    int sum = 0;
    int start = 0, end = 0;
    while (end < length)
    {
        sum += nums[end];
        while (sum > remain)
        {
            sum -= nums[start];
            start++;
        }
        if (sum == remain)
        {
            maxLength = Math.Max(maxLength, end - start + 1);
        }
        end++;
    }
    return maxLength < 0 ? -1 : length - maxLength;
}

[snmyj]

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int target = 0;
        for (int num : nums) target += num;
        target -= x;

        int sum = 0, len = -1;
        for (int l = 0, r = 0; r < nums.size(); r++) {
            sum += nums[r];
            while (l <= r && sum > target) sum -= nums[l++];
            if (sum == target) len = max(len, r - l + 1);
        }

        return len == -1 ? -1 : nums.size() - len;
    }
};

[Jetery]

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int target = 0;
        for (int num : nums) target += num;
        target -= x;

        int sum = 0, len = -1;
        for (int l = 0, r = 0; r < nums.size(); r++) {
            sum += nums[r];
            while (l <= r && sum > target) sum -= nums[l++];
            if (sum == target) len = max(len, r - l + 1);
        }

        return len == -1 ? -1 : nums.size() - len;
    }
};

[X1AOX1A]

class Solution:
    def solve(self, A, target):
        if not A and not target: return 0
        target = sum(A) - target
        ans = len(A) + 1
        i = t = 0

        for j in range(len(A)):
            t += A[j]
            while i <= j and t > target:
                t -= A[i]
                i += 1
            if t == target: ans = min(ans, len(A) - (j - i + 1))
        return -1 if ans == len(A) + 1 else ans

[linlizzz]

class Solution:
    def solve(self, A, target):
        if not A and not target: return 0
        target = sum(A) - target
        ans = len(A) + 1
        i = t = 0

        for j in range(len(A)):
            t += A[j]
            while i <= j and t > target:
                t -= A[i]
                i += 1
            if t == target: ans = min(ans, len(A) - (j - i + 1))
        return -1 if ans == len(A) + 1 else ans

[kofzhang]

思路

滑动窗口，两边减少k，即中间等于sum(nums)-k

复杂度

时间复杂度：O(n) 空间复杂度：O(1)

代码

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        s = sum(nums)
        req = s - x
        if req < 0:
            return -1
        l = 0
        cur = 0
        resmin = float(inf)
        for r in range(len(nums)):
            cur += nums[r]
            while cur>req:
                cur-=nums[l]
                l += 1

            if cur==req:
                resmin = min(resmin,len(nums)-r-1+l)

[JiangyanLiNEU]

• Sliding Window
• T = O(N)
• S = O(1)

  class Solution:
  def maxScore(self, cardPoints: List[int], k: int) -> int:
      # Get the minimum score in between
      res = float('inf')
      cur = 0
      midLength = len(cardPoints)-k
      for i in range(len(cardPoints)):
          if i >= midLength:
              cur -= cardPoints[i-midLength]
          cur += cardPoints[i]
          if i>=midLength-1: 
              res = min(res, cur)
      return sum(cardPoints) - res