search

leetcode-pp / 91alg-6-daily-check

91 算法第六期打卡仓库
28 stars 0 forks source link

【Day 47 】2022-01-27 - Number of Operations to Decrement Target to Zero #57

Open azl397985856 opened 2 years ago

azl397985856 commented 2 years ago

Number of Operations to Decrement Target to Zero

入选理由

暂无

题目地址

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

前置知识

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.

zwx0641 commented 2 years ago

class Solution { public int solve(int[] nums, int target) { //Arrays.sort(nums); int l = 0, r = 0; int sum = -target; for (int num : nums) { sum += num; } if (sum == 0) return nums.length; int cur = 0; int res = 0; while (r < nums.length) { cur += nums[r]; while (cur >= sum && r >= l) { if (cur == sum) { res = Math.max(res, r - l + 1); } cur -= nums[l]; l++; } r++; } return res == 0 ? -1 : nums.length - res; } }

yetfan commented 2 years ago

思路 滑动窗口找中间n个数字，使得剩下的数和为target。即中间n个数的和 = sum(nums) - target

代码

class Solution:
    def solve(self, nums, target):
        l = 0
        r = 0
        s = 0
        res = []
        rest_target = sum(nums) - target
        if rest_target < 0:
            return -1
        if rest_target == 0:
            return len(nums)

        while r < len(nums):
            s += nums[r]

            while s > rest_target:
                s -= nums[l] 
                l += 1

            if s == rest_target:
                res.append(len(nums) - (r-l+1))

            r += 1

        if res:
            return min(res)
        else:
            return -1

复杂度 时间 O(n) 空间 O(1) 可以列出n种可能性，也可以直接存最小值

ZhangNN2018 commented 2 years ago 
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
falconruo commented 2 years ago

思路:

滑动窗口

复杂度分析:

代码(C++):


class solution {
public:
    int solve(vector<int>& nums, int target) {
        if (target == 0) return 0;

        int len = nums.size();

        int sum = 0;

        for (auto n : nums)
            sum += n;

        int res = len;
        int winSum = sum - target;

        if (winSum == 0) return len;
        else if (winSum < 0) return -1;

        for (int r = 0, l = 0, tmpSum = 0; r < len; ++r) {
            tmpSum += nums[r];
            while (tmpSum >= winSum && l < len) {
                if (tmpSum == winSum)
                    res = min(len - r + l - 1, res);
                tmpSum -= nums[l];
                ++l;
            }
        }

        return res == len ? -1 : res;
    }
};
LAGRANGIST commented 2 years ago 
class Solution:
    def solve(self, nums, target):
        l = 0
        r = 0
        s = 0
        res = []
        rest_target = sum(nums) - target
        if rest_target < 0:
            return -1
        if rest_target == 0:
            return len(nums)

        while r < len(nums):
            s += nums[r]

            while s > rest_target:
                s -= nums[l] 
                l += 1

            if s == rest_target:
                res.append(len(nums) - (r-l+1))

            r += 1

        if res:
            return min(res)
        else:
            return -1
Tesla-1i commented 2 years ago 
class Solution:
    def solve(self, nums, target):
        l = 0
        r = 0
        s = 0
        res = []
        rest_target = sum(nums) - target
        if rest_target < 0:
            return -1
        if rest_target == 0:
            return len(nums)

        while r < len(nums):
            s += nums[r]

            while s > rest_target:
                s -= nums[l] 
                l += 1

            if s == rest_target:
                res.append(len(nums) - (r-l+1))

            r += 1

        if res:
            return min(res)
        else:
            return -1
dahaiyidi commented 2 years ago

Problem

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

++

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

Note

Complexity

Python

C++

#include <numeric>
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = std::accumulate(nums.begin(), nums.end(), 0);
        int target = sum - x;

        int i = 0, j= 0;
        sum = 0;
        int res = -1;
        while(j < nums.size()){

            // j右移，扩大窗口
            sum += nums[j++];

            //当sum>target, 需要i右移
            while(sum > target && i < nums.size()){
                sum -= nums[i++];
            }

            // 已经找到一种符合目标的情况
            if(sum == target){
                res = max(res, j - i);
            }

            // sum<target，进入下一个循环
        }
        return res != -1? nums.size() - res: -1;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

hdyhdy commented 2 years ago

思路：反求nums中连续元素和为sum-x的元素最大值。

func maxScore(cardPoints []int, k int) int {
    n := len(cardPoints)
    // 滑动窗口大小为 n-k
    windowSize := n - k
    // 选前 n-k 个作为初始值
    sum := 0
    for _, pt := range cardPoints[:windowSize] {
        sum += pt
    }
    minSum := sum
    for i := windowSize; i < n; i++ {
        // 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
        sum += cardPoints[i] - cardPoints[i-windowSize]
        minSum = min(minSum, sum)
    }
    total := 0
    for _, pt := range cardPoints {
        total += pt
    }
    return total - minSum
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

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

Zhang6260 commented 2 years ago

JAVA版本

主要是否能够转换问题，将原题的要求变成求滑动窗口的值为【数组所有的值的和减去target】

import java.util.*;

class Solution {
    public int solve(int[] nums, int target) {
        if(target==0)return 0;
        if(nums==null||nums.length==0)return -1;
        int res =nums.length+1;
        int temp = 0;
        int left = 0,right =nums.length-1;
        for(int i=0;i<nums.length;i++){
            temp+=nums[i];
            if(temp>=target){
                left = i;
                break;
            }
        }··
        if(temp<target)return -1;
        if(temp==target){
            res = Math.min(res,left+1);
        }
        while (left>=0){
            temp -= nums[left--];
            while (temp<target&&right>0){
                temp+=nums[right--];
            }
            if(temp==target)res=Math.min(res,left+nums.length-right);
        }
        return res==nums.length+1?-1:res;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

Aobasyp commented 2 years ago

思路 Sliding Window

int solve(vector& 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; // left: 滑动窗口左边界, i: 滑动窗口右边界right for (int i = 0; i < N; i++) { curSum += nums[i]; while (curSum >= newTarget && i >= left) // 寻找一个新的和为newTarget的滑动窗口区间 { if (curSum == newTarget) // 当找到的新的和为newTarget的滑动窗口区间更长时, 更新其长度 maxLen = max(maxLen, i - left + 1);

        curSum -= nums[left]; // 扔掉滑动窗口最左侧的数
        left++;
    }
}
return maxLen == 0 ? -1 : N - maxLen;

}

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

wenlong201807 commented 2 years ago

代码块


const minOperations = function (nums, x) {
  let len = nums.length,
    best = 0;
  for (let i = 1; i < len; i++) nums[i] += nums[i - 1];
  let y = nums[len - 1] - x;
  if (y < 0) return -1;
  if (y === 0) return len;
  for (let i = -1, j = (l = 0); i < len - best && l <= x; l = nums[++i]) {
    while (nums[j] - l < y) j++;
    if (nums[j] - l === y) best = Math.max(best, j - i);
  }
  return best > 0 ? len - best : -1;
};

时间复杂度和空间复杂度

wxj783428795 commented 2 years ago

思路

代码

class Solution {
    solve(nums, target) {
        let sums = nums.reduce((p, c) => p + c, 0);
        target = sums - target;
        if (nums.length === 0) {
            return target === 0 ? 0 : -1;
        } else {
            if (target === 0) return nums.length
        }
        let max = -1;

        let left = 0, right = 0;
        let subSum = 0;
        while (right < nums.length && left <= right) {

            subSum += nums[right];
            //console.log(subSum)
            while (subSum >= target) {
                if (subSum === target) {
                    max = Math.max(max, right - left + 1)
                }
                subSum -= nums[left];
                left++
            }
            right++;
        }
        return max === -1 ? -1 : nums.length - max;
    }
}

复杂度分析

haixiaolu commented 2 years ago

思路

滑动窗口

代码 / python

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

        left = right = 0
        for window_end in range(len(nums)):
            right += nums[window_end]
            while left <= window_end and right > target:
                right -= nums[left]
                left += 1

            if right == target:
                ans = min(ans, len(nums) - (window_end - left + 1))

        return -1 if ans == len(nums) + 1 else ans

复杂度分析

ZacheryCao commented 2 years ago

Idea

Sliding window + HashMap

Code

int solve(vector<int>& nums, int target) {
    if(nums.size() == 0){
        return target == 0? 0: -1;
    }
    if(target == 0) return 0;
    map<int, int> right = {{0, 0}};
    int ans = INT_MAX;
    int cur = 0;
    for(int i =0; i < nums.size(); i++){
        cur += nums[i];
        if(cur == target){
            ans = i+1;
        }
        if(cur > target){
            break;
        }
        right[cur]=i+1;
    }
    if(cur<target){
        return -1;
    }
    cur = 0;
    for(int i =nums.size()-1; i > -1; i--){
        cur += nums[i];
        if(cur > target){
            break;
        }
        if (right.find(target-cur) != right.end()){
            int new_length = nums.size()-i+right.find(target-cur)->second;
            if(new_length < ans){
                ans = new_length;
            }
        }
    }
    return ans == INT_MAX? -1:ans;
}

Complexity:

Time: O(N) Space: O(N)

ZZRebas commented 2 years ago

思路

遍历

代码(Python)

def fun(nums,target):
    nums.reverse()
    sum=0
    for i in range(len(nums)):
        sum+=nums[i]
        if sum==target:
            print(i+1)
            break
        elif sum>target:
            print(-1)
            break
        if i==len(nums)-1:
            print(-1)

nums = [3, 1, 1, 2, 5, 1, 1]
target = 7
fun(nums,target)

复杂度分析

XinnXuu commented 2 years ago 
class Solution {
    public int solve(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            if (target == 0)
                return 0;
            else
                return -1;
        }
        if (target == 0)
            return 0;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum == target)
            return n;
        target = sum - target;
        HashMap<Integer, Integer> map = new HashMap<>();
        int t = 0;
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            t += nums[i];
            if (t == target)
                ans = Math.min(n - 1 - i, ans);
            if (map.containsKey(t - target))
                ans = Math.min(ans, n - (i - map.get(t - target)));
            map.put(t, i);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
xvectorizer commented 2 years ago

将问题转化为找最长的子数组， sum(subarray) == target，使用滑动窗口解决

class Solution:
    def solve(self, nums, target):
        if not nums and target == 0:
            return 0

        ans = -1
        r = 0
        target = sum(nums) - target
        curr_sum = 0

        for l in range(len(nums)):
            while r < len(nums) and curr_sum < target:
                curr_sum += nums[r]
                r += 1

            if curr_sum == target:
                ans = max(ans, r - l)

            curr_sum -= nums[l]

        return len(nums) - ans if ans != -1 else -1
callmeerika commented 2 years ago

思路

滑动窗口，左指针向右遍历，然后右指针向左遍历，同时左指针向左回退

代码

  class Solution {
    solve(nums, target) {
      if (target === 0) return 0;
      let len = nums.length;
      let p = 0;
      let q = len - 1;
      let total = 0;
      let res = Infinity;
      while (p < len - 1) {
        total += nums[p];
        if (total === target) {
          res = Math.min(res, p + 1);
          break;
        } else if (total < target) {
          p++;
        } else {
          break;
        }
      }
      p = Math.min(p, len - 2);
      while (q > p) {
        total += nums[q];
        while (total > target && p >= 0) {
          total -= nums[p];
          p--;
        }
        if (total === target) {
          res = Math.min(res, len - q + p + 1);
          q--;
        } else if (total < target) {
          q--;
        } else {
          break;
        }
      }
      return res < Infinity ? res : -1;
    }
  }

复杂度

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

iambigchen commented 2 years ago

思路

可以转换成窗口大小固定的滑动窗口求最小值，这样剩下的就是最大值

关键点

代码

JavaScript Code:


/**
 * @param {number[]} cardPoints
 * @param {number} k
 * @return {number}
 */
var maxScore = function(cardPoints, k) {
    let sum = 0
    let min = 0
    let len = cardPoints.length - k
    cardPoints.forEach((e, index) => {
        if (index < len) {
            min += e
        }
        sum += e
    })
    let l = 1
    let r = len
    let res = min
    while(r < cardPoints.length) {
        min = min - cardPoints[l-1] + cardPoints[r]
        res = Math.min(res, min)
        l++
        r++
    }
    return sum - res
};

复杂度分析

令 n 为数组长度。

yan0327 commented 2 years ago

LC的1658题 思路： 求两边最小等于求中间最大，先对整个数组求和，减去target。然后开始求滑动窗口的值，

func minOperations(nums []int, x int) int {
    sum := 0
    for i:=0;i<len(nums);i++{
        sum += nums[i]
    }
    if sum == x{
        return len(nums)
    }
    if sum < x{
        return -1
    }
    sum -= x
    l, r := 0,0
    out := 0
    for ;r<len(nums);r++{
        sum -= nums[r]
        for sum < 0&&l <= r{
            sum += nums[l]
            l++
        }
        if sum == 0{
            if r-l+1 > out{
                out = r-l+1
            }
        }
    }
    if out == 0{
        return -1
    }
    return len(nums) - out
}

时间复杂度O（n） 空间复杂度O（1）

declan92 commented 2 years ago

步骤

  1. 求出sum(nums)-target;
  2. 初始化左右指针=0;移动右指针,累加数组和sum(nums);
    1. sum(nums)==target,打擂台记录最大长度;
    2. sum(nums)>target,移动左指针缩小窗口,数组和更新sum(nums);
      1. sum(nums)==target,打擂台记录最大长度;
      2. sum(nums)<target,继续移动右指针;
        java code 
        class Solution {
public int solve(int[] nums, int target) {
int sumNums = 0,sum = 0;
for(int i=0;i<nums.length;i++){
sumNums+=nums[i];
}
if(sumNums==target){
return nums.length;
}else if(sumNums<target){
return -1;
}
target = sumNums-target;
int left = 0,right = 0,length = -1;
while(right<nums.length){
sum+=nums[right++];
if(sum==target){
    length = Math.max(length,right-left);
}
while(sum>target){
    sum-=nums[left++];
    if(sum==target){
        length = Math.max(length,right-left);
    }
}
}
if(length==-1){
return -1;
}
return nums.length-length;
}
}

        时间:O(n)
        空间:O(1)

ZJP1483469269 commented 2 years ago 
class Solution:
    def solve(self, nums, target):
        sumnum = sum(nums)
        tar = sumnum - target
        if not target:
            return 0
        if sumnum < target:
            return -1
        if not tar:
            return len(nums)
        l = 0
        x = 0
        ans = -1
        xx = []
        for r in range(len(nums)):
            x += nums[r]

            while x >= tar:
                if x == tar:
                    ans = max(ans,r - l + 1)

                x -= nums[l]
                l += 1

        return   len(nums) - ans if ans != -1 else -1
yingliucreates commented 2 years ago 
const decTargetToZero = (arr, target) => {
  let leftIdx = 0;
  let rightIdx = arr.length - 1;
  let sumL = 0;
  let sumR = 0;
  let foundL = false;
  let foundR = false;

  while (leftIdx < arr.length - 1 && sumL <= target) {
    if (sumL === target) {
      foundL = true;
      break;
    }
    sumL += arr[leftIdx];
    leftIdx++;
  }

  while (rightIdx > 0 && sumR <= target) {
    if (sumR === target) {
      foundR = true;
      break;
    }
    sumR += arr[rightIdx];
    console.log(sumR);
    rightIdx--;
  }

  console.log(leftIdx, rightIdx);

  if (foundL && !foundR) return leftIdx + 1;
  if (foundR && !foundL) return arr.length - rightIdx;
  if (foundL && foundR) return Math.min(leftIdx, arr.length - rightIdx - 1);
  return -1;
};
linyang4 commented 2 years ago

思路

滑动窗口

  1. 先求出 nums 的总和 sum, 然后维护一个窗口, 如果存在这么一个窗口, 使得窗口的总和 windowSum = sum - target, 此时窗口外的元素总和就是 target 了, 删除窗口外元素即可满足题目条件.
  2. 注意: 可能会有多个满足条件的窗口, 由于窗口内元素越多, 需要删除的窗口外的元素就越少, 那么我们就需要找满足条件的最大的窗口

代码(JavaScript)

class Solution {
    solve(nums, target) {
        if (target === 0) { return 0 }
        const sum = nums.reduce((calc, num) => calc += num, 0)
        if (sum < target) { return -1 }
        let left = 0, right = 0, ans = -1, windowSum = 0
        while(right < nums.length) {
            windowSum += nums[right]
            while (windowSum >= sum - target) {
                if (windowSum === sum - target) {
                    const count = nums.length - (right - left + 1)
                    ans = (ans === -1 || count < ans) ? count : ans
                }
                windowSum -= nums[left]
                left++
            }
            right++
        }
        return ans
    }
}

复杂度

Liuxy94 commented 2 years ago

思路

参考题解 滑动窗口 + 二分法

代码

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

复杂度分析

时间： O(n)

空间：O(1)

zhangzhengNeu commented 2 years ago

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
cszys888 commented 2 years ago 
class Solution:
    def solve(self, nums, target):
        if target == 0:
            return 0
        psum = sum(nums)
        if psum < target:
            return -1
        ans = len(nums) + 1
        ssum = 0
        ssumcnt = 0
        for i in range(len(nums)-1, -1, -1):
            psum -= nums[i]
            while psum + ssum < target:
                ssum += nums[-1-ssumcnt]
                ssumcnt += 1
            if psum + ssum == target:
                ans = min(ans, i+ssumcnt)
        if ans > len(nums):
            return -1
        return ans

time complexity: O(N) space complexity: O(1)

zhangzz2015 commented 2 years ago 

int solve(vector<int>& nums, int target) {
  ///    transfer this question to  
  // 
     // find   [i  j]   =  totalSum - target;
     //        [i  j] = preSum[j] - preSum[i-1]; 
     if(target == 0)
      return 0; 
     int sum=0; 
     vector<int> preSum(nums.size()+1, 0);
     for(int i=0; i< nums.size(); i++)
     {
        sum += nums[i]; 
        preSum[i+1] = sum; 
     }
     if(sum<target)
        return -1; 
     target = sum - target;    
     unordered_map<int, int>  record;
     record[0] =0;
     int ret = INT_MIN;      
     for(int i=0; i< preSum.size(); i++){
         int val = preSum[i] - target;
         if(record.count(val))
         {           
            ret = max(ret, i - record[val]); 
         }
         record[preSum[i]] =i; 
     }   
     return ret==INT_MIN? -1: nums.size() - ret;      
}
biscuit279 commented 2 years ago

思路：

转化成寻找和为sum-target的最长子数组的长度

class Solution:
    def solve(self, nums, target):
        if not nums and not target:
            return 0
        if not nums and target:
            return -1
        target = sum(nums) - target #转换成和为sum-target的最小连续子串
        ans = len(nums)+1
        i = t = 0

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

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

feifan-bai commented 2 years ago

思路

  1. 滑动窗口 + 二分

代码

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

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

复杂度分析

xuhzyy commented 2 years ago

思路

滑动窗口

代码

class Solution:
    def solve(self, nums, target):
        n = len(nums)
        target = sum(nums) - target
        if target < 0:
            return -1
        if target == 0:
            return n
        l, r, window, lenth = 0, 0, 0, 0
        while(r < n):
            window += nums[r]
            while(window >= target):
                if window == target:
                    lenth = max(lenth, r - l + 1)
                window -= nums[l]
                l += 1
            r += 1
        return n - lenth if lenth > 0 else -1

复杂度分析

Yachen-Guo commented 2 years ago 
class Solution {
    // 一共 len 张卡牌
    // 每次从头部或者尾部取一张卡牌，一共取K次，要求，取出的卡牌之和最大
    // 等价于剩下的 len - K 张卡牌之和最小
    // 并且剩下的len - K张卡牌必须是连续的
    // 因此很容易想到滑动窗口
    public int maxScore(int[] cardPoints, int k) {
        int len = cardPoints.length;
        int min = 0;  // 记录已知的len-k张卡牌之和的最小值
        int now = 0;  // 记录当前的len-k张卡牌之和
        int total = 0;// 记录卡牌总和
        int rest = len - k;  // 需要剩下的卡牌数量，即滑动窗口大小
        for (int i = 0 ; i < rest ; i ++){
            now += cardPoints[i];  //  第0 到 第len-k张卡牌之和
        }
        min = now;
        total = now;
        for (int i = rest ; i < len ; i ++){
            now = now + cardPoints[i]; // 每次移动窗口都加上窗口右边的一个元素
            now = now - cardPoints[i - rest];  // 同时减去左边的元素
            min = Math.min(min,now);    // 更新最小值
            total = total + cardPoints[i];   // 记录卡牌总和
        }
        return total - min; // 卡牌总和减去剩下卡牌的最小值 = 取走卡牌的最大值
    }
}
LannyX commented 2 years ago

思路

滑动

代码

LeetCode 1658
class Solution {
    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int l = 0, r = 0, sum = 0, sumNum = 0;
        int maxLen = -1;
        for(int num : nums){
            sum += num;
        }
        int count = sum - x;
        if(count < 0){
            return -1;
        }
        while(r < n){
            sumNum += nums[r];
            while(sumNum > count){
                sumNum -= nums[l];
                l++;
            }
            if(sumNum == count){
                maxLen = Math.max(maxLen, r - l + 1);
            }
            r++;
        }
        if(maxLen == -1) return -1;
        else return n - maxLen;
    }
}

LeetCode 1423
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int i = 0, ms = 0, k2 = k;

        for(; i < k; i++){
            ms += cardPoints[i];
        }
        int max = ms;
        for(int r = n - 1; r >= n - k; r--){
            ms = ms + cardPoints[r] - cardPoints[--i];
            if(ms > max){
                max = ms;
            }
        }
        return max;
    }
}

复杂度分析

tongxw commented 2 years ago

思路

找连续子串的和为sum(nums) - target

class Solution {
    public int solve(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if (sum < target) {
            return -1;
        }
        if (sum == target) {
            return nums.length;
        }

        int winSum = 0;
        int maxLen = 0;
        int left = 0;
        for (int right=0; right<nums.length; right++) {
            winSum += nums[right];
            while (winSum > sum - target && left <= right) {
                winSum -= nums[left];
                left++;
            }

            if (winSum == sum - target) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }

        return maxLen == 0 ? -1 : nums.length - maxLen;
    }
}

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

Myleswork commented 2 years ago

思路

滑动窗口

要删的是两边的，不连续，那留下来的是中间的，这不就连续了么。

所以转换思想，就是要找出和不大于sum-target的连续子序列，最后返回len-子序列的长度即可

代码

int solve(vector<int>& nums, int target) {
    int sum = accumulate(nums.begin(),nums.end(),0) - target;
    if(sum<0) return -1;
    int len = nums.size();
    if(sum == 0) return len;
    int l = 0;
    int maxlen = 0;
    int count = 0;
    for(int r = 0;r<len;r++){
        count+=nums[r];
        while(count>=sum){
            if(count == sum) maxlen = max(r-l+1,maxlen);
            count-=nums[l++];
        }
    }
    return maxlen == 0?-1:len-maxlen;
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

tian-pengfei commented 2 years ago 
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {

        int sum= 0;
        for (int num:cardPoints){
            sum+=num;
        }
//       滑动窗口的大小已经固定，滑动窗口的值最小时值，手中的牌拿到的最大

              int size  = cardPoints.size();
        int w_size =size-k;

        int pos1 = 0;
        int pos2 = 1;
        int rest_sum = 0;
        int min_rest_sum=0;
        while (pos2<=size){
            rest_sum+=cardPoints[pos2-1];
            if(pos2++<=w_size){
                min_rest_sum = rest_sum;
                continue;
            }
            rest_sum-=cardPoints[pos1++];
            min_rest_sum = min(min_rest_sum,rest_sum);
        }

        return sum-min_rest_sum;

    }

};
JudyZhou95 commented 2 years ago

代码

class Solution:
    def solve(self, nums, target):
        if not target:
            return 0
        if not nums:
            return -1

        inner_target = sum(nums) - target
        i = 0
        s = 0
        res = len(nums) + 1

        for j in range(len(nums)):
            s += nums[j]

            while i <= j and s > inner_target:
                s -= nums[i]
                i += 1

            if s == inner_target:
                res = min(res, len(nums) - (j - i + 1))

        return -1 if res == len(nums)+1 else res

复杂度

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

kbfx1234 commented 2 years ago

Number of Operations to Decrement Target to Zero

// 1-27
int solve(vector<int>& nums, int target) {
    if (target == 0) return 0;
    if (nums.size() == 0) return -1;
    int sum = 0, k = 0;
    for (auto i : nums) sum += i;
    k = sum - target;
    if (sum < target) return -1;

    int len = nums.size();
    if (sum == target) return len;

    int l = 0, r = -1, winsum = 0, ans = len + 1;
    while (r < len) {
        winsum += nums[++r];
        while (winsum >= k && l <= r) {
            if (winsum == k) ans = min(ans, len-r+l-1);
            winsum -= nums[l++];
        }
    }
    return ans == len + 1 ? -1 : ans;
}
charlestang commented 2 years ago

思路：滑动窗口

  1. 因为只需要求最小长度，所以，我们只需要知道，所有数字的总和 sum - target 的最大长度，剩下的自然就是 prefix 和 suffix 组成 target 的最小长度。

时间复杂度 O(n)

空间复杂度 O(n)

代码

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n, l, r, s = len(nums), -1, 0, 0
        target = sum(nums) - x
        ans = -1
        while r < n:
            s += nums[r]
            r += 1
            if s < target:
                continue
            while s > target and l < n - 1:
                l += 1
                s -= nums[l]
            if s == target:
                ans = max(ans, r - l - 1)
        return ans if ans < 0 else (n - ans)
stackvoid commented 2 years ago

思路

滑动窗口

代码

class Solution {
    public int solve(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if (sum < target) {
            return -1;
        }
        if (sum == target) {
            return nums.length;
        }

        int winSum = 0;
        int maxLen = 0;
        int left = 0;
        for (int right=0; right<nums.length; right++) {
            winSum += nums[right];
            while (winSum > sum - target && left <= right) {
                winSum -= nums[left];
                left++;
            }

            if (winSum == sum - target) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }

        return maxLen == 0 ? -1 : nums.length - maxLen;
    }
}

算法分析

Time O(N) SpaceO(1)

biaohuazhou commented 2 years ago

思路

滑动窗口

代码

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        //逆向思维  我们可以通过求出剩余卡牌点数之和的最小值，来求出拿走卡牌点数之和的最大值
        //由于剩余卡牌是连续的，使用一个固定长度为 n-k 的滑动窗口对数组
        //cardPoints 进行遍历，求出滑动窗口最小值，然后用所有卡牌的点数之和减去该最小值，即得到了拿走卡牌点数之和的最大值。
        int sum=0,minSum=0;
       int n=cardPoints.length;
        for (int i = 0; i <n ; i++) {
            sum+=cardPoints[i];
        }
        for (int i = 0; i <n-k ; i++) {
            minSum+=cardPoints[i];
        }
        int tmpsum=minSum;
        for (int i = n-k; i <n; i++) {
            tmpsum+=cardPoints[i]-cardPoints[i-(n-k)];
            minSum=Math.min(minSum,tmpsum);
        }
        return sum-minSum;

    }
}

复杂度分析 时间复杂度：$O(n)$ n为卡牌长度 空间复杂度：$O(1)$

machuangmr commented 2 years ago

代码

import java.util.*;

class Solution {
    public int solve(int[] nums, int target) {
        int len = nums.length;
        int sum = 0;
        for(int i = 0;i < len;i++) {
            sum += nums[i];
        }
        int newTarget = sum - target;
        if(newTarget == 0) return len;
        int left = 0;
        int curSum = 0;
        int maxLen = 0;
        for(int i = 0;i < len;i++) {
            curSum += nums[i];
            while(curSum >= newTarget && i >= left) {
                if(curSum == newTarget) {
                    maxLen = Math.max(maxLen, i - left + 1);
                }
                curSum -= nums[left];
                left++;
            }
        }
        return maxLen == 0 ? -1 : len - maxLen;
    }
}

复杂度

Flower-F commented 2 years ago

解题思路

滑动窗口，题目难度不大，但是这个边界判定把我坑死了，wa了几发

代码

class Solution {
    solve(nums, target) {
        if (target === 0) {
            return 0;
        }
        if (nums.length === 0) {
            return -1;
        }

        // 即求解和为 sum - target 的连续子数组
        // 求解出最长的满足条件的数组，即为需要弹出最少数字的数组
        const sum = nums.reduce((pre, cur) => (pre + cur)) - target;

        if (sum === 0) {
            return nums.length;
        }

        let left = 0, right = 0;
        let curSum = 0, maxLen = 0;

        while (right < nums.length) {
            const num = nums[right++];
            curSum += num;

            while (left < right && curSum >= sum) {
                if (curSum === sum) {
                    maxLen = Math.max(maxLen, right - left);
                }

                const num = nums[left++];
                curSum -= num;
            }
        }

        return maxLen === 0 ? -1 : nums.length - maxLen;
    }
}

复杂度

时间：O(N) 空间：O(1)

KevinWorkSpace commented 2 years ago 
class Solution {
    public int solve(int[] nums, int target) {
        if(target==0)return 0;
        if(nums==null||nums.length==0)return -1;
        int res =nums.length+1;
        int temp = 0;
        int left = 0,right =nums.length-1;
        for(int i=0;i<nums.length;i++){
            temp+=nums[i];
            if(temp>=target){
                left = i;
                break;
            }
        }··
        if(temp<target)return -1;
        if(temp==target){
            res = Math.min(res,left+1);
        }
        while (left>=0){
            temp -= nums[left--];
            while (temp<target&&right>0){
                temp+=nums[right--];
            }
            if(temp==target)res=Math.min(res,left+nums.length-right);
        }
        return res==nums.length+1?-1:res;
    }
}
xinhaoyi commented 2 years ago

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

思路一：递归(超时)

代码

import java.util.*;

class Solution {
    public int solve(int[] nums, int target) {
        int res = recursionSolve(nums, 0, nums.length - 1, target);
        return res == Integer.MAX_VALUE ? -1 : res;
    }
    public int recursionSolve(int[] nums, int left, int right, int target){
        if(target==0) return nums.length - (right - left + 1);
        if(target<0) return Integer.MAX_VALUE;
        if(left > right) return Integer.MAX_VALUE;
        int leftTimes = recursionSolve(nums,left+1,right,target-nums[left]);
        int rightTimes = recursionSolve(nums,left,right-1,target-nums[right]);
        return Math.min(leftTimes,rightTimes);
    }
}

思路二：前缀和+二分(通过)

public int solve(int[] nums, int target)

sum = sumOfNum - target = prefixSum[right] - prefixSum[left]

num中可能有若干子列满足和为sum

我们构造一个长度为N+1的前缀和数组predixSum[ N+1 ] (N为sumOfNum.length)

这样，predixSum[ right ] - predixSum[ left ] 表示数组nums中下标为left的数到下标为right - 1的数的和

我们固定 i = left(每回合i增加1)，二分法不断寻找合适的mid，使得sum = sumOfNum - target = prefixSum[mid] - prefixSum[left]

一旦找到mid，它在原nums中对应着mid - 1的下标，从 i 到mid - 1有 (mid - 1 - i + 1)个元素，记为count个

然后我们用nums.length - count 就得到了移走了多少个元素，找到这个最小值就是我们的答案

代码

public class Solution {
    public int solve(int[] nums, int target) {
        //sumOfNum - target = prefixSum[right] - prefixSum[left];
        //sumOfNum - target = prefixSum[mid] - prefixSum[left];
        int sumOfNum = 0;
        for(int num : nums){
            sumOfNum += num;
        }
        int sum = sumOfNum - target;
        if(sum < 0) return -1;
        int[] prefixSum = new int[nums.length + 1];
        prefixSum[0] = 0;
        //generate the prefixSum
        for(int i = 1; i < prefixSum.length; i++){
            prefixSum[i] = prefixSum[i-1] + nums[i-1];
        }
        int res = Integer.MAX_VALUE;
        int cur = Integer.MAX_VALUE;
        for(int i = 0; i <= nums.length; i++){
            int left = i;
            int right = nums.length;
            while(left <= right){
                int mid = (left + right) / 2;
                if((prefixSum[mid] - prefixSum[i]) == sum){
                    cur = nums.length - (mid - i);
                    res = Math.min(cur,res);
                    break;
                }
                else if((prefixSum[mid] - prefixSum[i]) < sum){
                    //mid is smaller
                    left = mid + 1;
                }
                else{
                    //mid is larger
                    right = mid - 1;
                }
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,1,1,2,5,1,1};
        int target = 7;
        System.out.println(new Solution().solve(nums, target));
    }
}
ReadyCheng commented 2 years ago

class Solution { public int solve(int[] nums, int target) { if(target==0)return 0; if(nums==null||nums.length==0)return -1; int res =nums.length+1; int temp = 0; int left = 0,right =nums.length-1; for(int i=0;i<nums.length;i++){ temp+=nums[i]; if(temp>=target){ left = i; break; } }·· if(temp<target)return -1; if(temp==target){ res = Math.min(res,left+1); } while (left>=0){ temp -= nums[left--]; while (temp<target&&right>0){ temp+=nums[right--]; } if(temp==target)res=Math.min(res,left+nums.length-right); } return res==nums.length+1?-1:res; } }

junbuer commented 2 years ago

思路

代码

class Solution:
    def solve(self, nums, target):
        diff = sum(nums) - target
        n = len(nums)
        if diff < 0:
            return -1
        elif diff == 0:
            return n

        l, r, cnt = 0, 0, 0
        res = 0

        while r < n:
            cnt += nums[r]
            while cnt > diff:
                cnt -= nums[l]
                l += 1
            if cnt == diff:
                res = max(res, r - l + 1)
            r += 1

        return n - res if res > 0 else -1

复杂度分析

1149004121 commented 2 years ago

Number of Operations to Decrement Target to Zero

思路

滑动窗口

代码

class Solution {
  solve(nums, target) {
    const n = nums.length;
    let res = n + 1;
    let l = 0;
    let sum = 0;
    let total = 0;
    for (let num of nums) {
      total += num;
    };
    for (let r = 0; r < n; r++) {
      sum += nums[r];
      while (sum > total - target) {
        sum -= nums[l];
        l++;
      };
      if (sum === total - target) res = Math.min(res, n - r + l - 1);
    };
    return res === n + 1 ? -1 : res;
  };
}

复杂度分析

GaoMinghao commented 2 years ago

思路

学到了 学到了 果然还是刷题刷的少，常见的思路也想不出来😂，转换思维，然后滑动窗口，跟昨天相比的是判断左边界是否收缩的判断条件需要注意下

代码

import java.util.*;

class Solution {
    public int solve(int[] nums, int target) {
        int sum = 0;
        for(int num:nums) sum += num;
        if(target == sum)
            return nums.length;
        target = sum - target;
        if(target < 0)
            return -1;
        int left = 0, right = 0, length = Integer.MIN_VALUE;
        int window = 0;
        while(right < nums.length) {
            window += nums[right++];
            while(window >= target) {
                if(window == target && right - left > length) {
                    length = right - left;
                }
                window = window-nums[left++];
            }
        }
        return length == Integer.MIN_VALUE ? -1: nums.length-length;
    }
}

复杂度

时间复杂度 O(n)

shamworld commented 2 years ago 
class Solution {
    solve(nums, target) {
        if(!nums.length&&!target) return 0;
        let len = nums.length,
            best = 0;
        for (let i = 1; i < len; i++) nums[i] += nums[i - 1];
        let y = nums[len - 1] - target;
        if (y < 0) return -1;
        if (y === 0) return len;
        for (let i = -1, j = 0,l = 0; i < len - best && l <= target; l = nums[++i]) {
            while (nums[j] - l < y) j++;
            if (nums[j] - l === y) best = Math.max(best, j - i);
        }
        return best > 0 ? len - best : -1;
    }
}