【Day 47 】2021-10-26 - Number of Operations to Decrement Target to Zero #64
Comments
思路题意: 给你一个正整数数组nums和一个整数target。每一次操作，只能从nums数组的最前面或最后面删除一个数字v，同时将target减去v。 返回将target减为零所需的最少操作次数。如果不可能做到，则返回-1。 限制条件 n ≤ 100,000，其中n是nums的长度。 问题转换题目要求删掉数组nums的左右两端的元素，并且删掉的元素和为target，也就是留下中间连续的子数组，其和为sum(nums) - target; 那么问题就转化为了找数组中间和为sum(nums) - target的最长子数组，令该表达式为我们的新目标new_target, 并将原数组的长度记作N。 使用滑动窗口接下来就可以用滑动窗口来求和为newTarget的滑动窗口的最大长度了:
代码实现语言: C++ 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; // 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;
}复杂度分析
|
int solve(vector<int>& nums, int target) {
if (target == 0) return 0;
int N = nums.size(), msum = accumulate(nums.begin(), nums.end(), 0) - target, ans = INT_MAX;
if (msum <= 0) return msum == 0 ? N : -1;
unordered_map<int, int> m{{0, -1}};
for (int i = 0, s = 0; i < N; i++) {
s += nums[i];
auto it = m.find(s - msum);
if (it != m.end()) ans = min(ans, N - (i - it->second));
if (!m.count(s)) m[s] = i;
}
return ans == INT_MAX ? -1 : ans;
} |
代码
C++ Code: int solve(vector<int>& nums, int target) {
int sum = 0;
for(int i=0;i<nums.size();i++)
sum += nums[i];
target = sum - target;
if(target==0)
return nums.size();
else if(target<0)
return -1;
int l = 0, r = 0, max_val = 0;
sum = 0;
while(r<nums.size())
{
sum += nums[r];
while(sum>target)
{
sum -= nums[l];
l++;
}
if(sum==target)
max_val = max(max_val,r - l + 1);
r++;
}
if(max_val==0)
return -1;
return nums.size() - max_val;
}
复杂度分析 令 n 为数组长度。
|
思路
int solve(vector<int>& nums, int target) {
/// [i j] --- > sum = total - target;
if(target ==0)
return 0;
int sum =0;
for(int i=0; i< nums.size(); i++)
{
sum += nums[i];
}
sum = sum - target;
if(sum<0)
return -1;
int left =0;
int right =0;
int ret = -1;
while(right < nums.size())
{
sum -= nums[right];
while(sum<0)
{
sum +=nums[left];
left++;
}
if(sum==0)
{
ret = max(ret, right - left + 1);
}
right++;
}
return ret==-1? -1 : nums.size() - ret;
} |
通过arraySum - target将问题转化为求最长subarray代码部分：class Solution {
public int solve(int[] nums, int target) {
int t = - target;
for (int num: nums) t += num;
if (t == 0) return nums.length; // 此时最长subarray就是原数组
if (t < 0) return -1;
int left = 0, sum = 0, L = 0;
for (int right = 0; right < nums.length; right ++) {
sum += nums[right];
while (sum > t) {
sum -= nums[left ++];
}
if (sum == t) {
L = Math.max(L, right - left + 1);
}
}
return L > 0 ? nums.length - L : -1;
}
}复杂度：Time: O(n)Space: O(1) |
思路将问题转化为找到和为k的最长的连续数组问题。用滑动窗口模板。 代码class Solution:
def solve(self, nums, target):
# 中间的subarray = sum - target,且要保证这个长度最长
# 转化成了找到和是subarray的最长的连续数组
# 用滑动窗口的模板
# 长度right - left + 1
if sum(nums) < target:
return -1
if sum(nums) == target:
return len(nums)
left = 0
subsum = sum(nums) - target
temp = 0
steps = 0
for right in range(len(nums)):
temp += nums[right]
while temp >= subsum and left <= right:
if subsum == temp:
steps = max(steps, right - left + 1)
# 开始扔左边的元素，因为进入while loop的时候一定是temp >= subsum的时候，也就是满足条件的时候
temp -= nums[left]
left += 1
return -1 if steps == 0 else len(nums) - steps复杂度分析时间复杂度：O(n) |
|
Convert to a sliding window problem. class Solution:
def solve(self, nums, target):
ss = sum(nums)
if target == 0: return 0
if ss < target: return -1
if ss == target: return len(nums)
target = ss - target
#max sliding window sum to target
l = 0
ret = -1
ss = 0
for r in range(len(nums)):
n = nums[r]
ss += n
while ss > target and r > l:
ss -= nums[l]
l += 1
if ss == target:
ret = max(ret, r - l + 1)
return len(nums) - ret if ret > 0 else -1 |
Sliding Window
JavaScript Codeclass Solution {
solve(nums, target) {
// Get the sum of array
let sum = 0;
for (let num of nums){
sum+= num;
};
// Edge cases
if (sum<target){
return -1;
}else if (sum===target){
return nums.length;
}
// target sum of window
let targetSum = sum-target;
// sliding window to find the longest sub array
// find the starting left point
let left = 0;
while (nums[left]>targetSum){
left++;
if (left==nums.length){
return -1
};
};
let right = left;
let curSum = nums[left];
let result = Math.pow(10, 1000);
// move the window
while (right<nums.length){
if (curSum == targetSum){
result = result>nums.length-(right-left+1) ? nums.length-(right-left+1) : result;
curSum -= nums[left];
left++;
}else if (curSum > targetSum){
curSum -= nums[left];
left++;
}else if(curSum < targetSum){
right++;
if (right==nums.length){
return result == Math.pow(10, 1000) ? -1 : result;
}else{
curSum += nums[right];
};
if (left>right){
right = left;
if (right==nums.length){
return -1;
}else{
curSum += nums[right];
};
};
};
};
}
}Python Codeclass Solution:
def solve(self, nums, target):
summ = sum(nums)
length = len(nums)
if summ < target:
return -1
if summ == target:
return len(nums)
inSum = summ-target
left = 0
result = float('inf')
while nums[left] > inSum:
left += 1
if left == length:
return -1
right = left
cur = nums[left]
while right<length:
if cur == inSum:
result = min(result, length-(right-left+1))
left += 1
cur -= nums[left-1]
elif cur > inSum:
left += 1
cur -= nums[left-1]
elif cur < inSum:
right += 1
if right == length:
return -1 if result == float('inf') else result
cur += nums[right] |
Idea:Sliding widow. The longest window whose value is sum(nums) - target Code:class Solution:
def solve(self, nums, x):
if not x:
return 0
if not nums or nums[0] > x and nums[-1] > x :
return -1
n = sum(nums)
k = n - x
if n < x:
return -1
l ,r, cur = 0, 0, 0
ans = math.inf
while r < len(nums):
cur += nums[r]
while cur > k:
cur -= nums[l]
l += 1
if cur == k:
ans = min(ans, len(nums) - (r - l + 1))
r += 1
return ans if ans != math.inf else -1Complexity:Time: O(N) |
思路滑动窗口. 一定要注意 edge cases 代码
Java Code: class Solution {
public int solve(int[] nums, int target) {
int sum = Arrays.stream(nums).sum();
if (sum - target < 0) {
return -1;
}
if (sum - target == 0) {
return nums.length;
}
int ret = longestSubarraySumEqualsK(nums, sum - target);
return ret == -1? ret: nums.length - longestSubarraySumEqualsK(nums, sum - target);
}
public int longestSubarraySumEqualsK(int[] nums, int k) {
int slow = 0;
int curSum = 0;
int maxLen = 0;
for (int fast = 0; fast < nums.length; fast++) {
curSum += nums[fast];
while (slow <= fast && curSum > k) {
curSum -= nums[slow++];
}
if (curSum == k) {
if (fast - slow + 1 > maxLen) {
maxLen = fast - slow + 1;
}
}
}
return maxLen == 0? -1: maxLen; // 注意 handle 不可能的情况
}
}复杂度分析 令 n 为数组长度。
|
思路滑动窗口。 代码(C++)int solve(vector<int>& nums, int target) {
int sum = 0, res = -1, left = 0, right = 0, curSum = 0;
for(int i = 0; i < nums.size(); i++) sum += nums[i];
int tar = sum - target;
if (tar == 0) return nums.size();
while (right < nums.size()) {
curSum += nums[right];
while (curSum >= tar) {
if (curSum == tar) res = max(res, right - left + 1);
curSum -= nums[left++];
}
right++;
}
return res == -1 ? -1 : nums.size() - res;
}复杂度分析
|
Day 47: 843. Number of Operations to Decrement Target to Zero (sliding window)
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
#transform this problem to: find the maximum subarray which sums to sum(nums) - target
class Solution:
def solve(self, nums, target):
#if target == 0: return 0
#if sum(nums) < target: return -1
if sum(nums) == target: return len(nums)
sum_remain = sum(nums) - target
max_len = 0
left = 0
cur_sum = 0
for right, num in enumerate(nums):
cur_sum += num
while cur_sum > sum_remain and left <= right: #if we add this left <= right, the first two if could be removed!
cur_sum -= nums[left]
left += 1
if cur_sum == sum_remain:
max_len = max(max_len, right - left + 1)
print (max_len)
return len(nums) - max_len if max_len != 0 else -1 #max_len = 0 or not could not distinguish [2,2] 3 and [1] 1, have to add several conditions at the beginning
|
class Solution:
def solve(self, nums, target):
target = sum(nums) - target
if target == 0:
return len(nums)
elif target < 0:
return -1
l = total = res = 0
for r in range(len(nums)):
total += nums[r]
while total > target:
total -= nums[l]
l += 1
if total == target:
res = max(res, r-l+1)
return len(nums) - res if res > 0 else -1 |
|
Explanation
Python class Solution:
def solve(self, nums, target):
s = sum(nums)
if s == target:
return len(nums)
elif s < target:
return -1
else:
maxLength = 0
newTarget = sum(nums) - target
left, currSum = 0, 0
for i in range(len(nums)):
currSum += nums[i]
while currSum > newTarget:
currSum -= nums[left]
left += 1
if currSum == newTarget:
maxLength = max(maxLength, i-left+1)
return len(nums)-maxLength if maxLength != 0 else -1Complexity:
|
class Solution:
def solve(self, nums, target):
if not nums and not target:
return 0
n = len(nums)
target = sum(nums) - target
ans = float('inf')
i = total = 0
for j in range(n):
total += nums[j]
while i <= j and total > target:
total -= nums[i]
i += 1
if target == total:
ans = min(ans, n - (j - i + 1))
return -1 if ans == float('inf') else anstime complexity: O(n) |
Title:Number of Operations to Decrement Target to ZeroQuestion Reference LeetCodeSolutionLet's say the after adding up all the items in the array, the total is sum. To find the largest sub-array, we use a map, the key is the cumulative sum so far, and the value is the index for the cumulative sum. Each time we got a new cumulative sum for current index i, sum(i), we try to see if sum(i) - sum(sub_array) is in the map, if so, we have found a candidate. Codeint solve(vector<int>& nums, int target) {
if (!target)
return 0;
int total = 0;
int len = 0;
for (int num : nums) {
total += num;
}
int tar = total - target;
if (!tar)
return nums.size();
unordered_map<int, int> data_store;
data_store[0] = -1;
int cur = 0;
for (int i = 0; i < nums.size(); i++) {
cur += nums[i];
if (!data_store.count(cur)) {
data_store[cur] = i;
}
if (data_store.count(cur - tar) && (i - data_store[cur - tar]) > len) {
len = i - data_store[cur - tar];
}
}
return len? nums.size() - len : -1;
}
ComplexityTime Complexity and ExplanationO(n), we visit each item in the array twice Space Complexity and ExplanationO(n), we need to use map to store the cumulative sum and its index |
思路官方题解思路，转化问题，滑动窗口（思路真的学习到了） 代码
C++ Code: 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;
}
};
复杂度分析 令 n 为数组长度。
|
思路使用滑动窗口的方法, 想要找到最大的窗口, 需要窗口中的和是 t = sum (nums) - target 每次将元素加入窗口, 如果此时的和大于 t, 那么右移窗口的左边界, 直到窗口中的数的和小于等于 t 检查 窗口中的数的和是否等于 t, 如果等于, 那么 跟 min_length 比较并更新 min_length class Solution:
def solve(self, nums, target):
if nums == []:
return -1 if target != 0 else 0
s,l = 0,0
t = sum(nums) - target
min_length = len(nums)+1
for i, n in enumerate(nums):
s += n
while s > t and l <= i:
s -= nums[l]
l += 1
if s == t:
min_length = min(min_length, len(nums) - (i-l+1))
return -1 if min_length == len(nums)+1 else min_length复杂度时间复杂度: O(n) 一次遍历的时间复杂度 空间复杂度: O(1) |
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;
}
}; |
思路滑动窗口 class Solution:
def solve(self, nums, target):
if nums == []:
return -1 if target != 0 else 0
s,l = 0,0
t = sum(nums) - target
min_length = len(nums)+1
for i, n in enumerate(nums):
s += n
while s > t and l <= i:
s -= nums[l]
l += 1
if s == t:
min_length = min(min_length, len(nums) - (i-l+1))
return -1 if min_length == len(nums)+1 else min_length复杂度
|
# to find min operation: find max sublist length that has sum of total - target
# sliding window: increment right if window sum < total - target, otherwise increment left
# time: O(N)
# space: O(1)
class Solution:
def solve(self, nums, target):
total = sum(nums)
if total < target:
return -1
if total == target:
return len(nums)
left = 0
curr_sum = 0
# max valid sublist length that hs sum total - target
max_length = -1
for right in range(len(nums)):
curr_sum += nums[right]
while left < right and curr_sum > total - target:
curr_sum -= nums[left]
left += 1
if curr_sum == total - target:
max_length = max(max_length, right - left + 1)
if max_length == -1:
return -1
return len(nums) - max_length |
思路二分法、滑动窗口 代码Python3 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复杂度
|
|
LC的1658题 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） |
思路其实就是求和 = sum - 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) {
if (winSum == sum - target) {
maxLen = Math.max(maxLen, right - left + 1);
}
winSum -= nums[left];
left++;
}
}
return maxLen == 0 ? -1 : nums.length - maxLen;
}
}TC: O(n) |
Number of Operations to Decrement Target to Zerohttps://binarysearch.com/problems/Number-of-Operations-to-Decrement-Target-to-Zero Topics
思路slide window 代码 Pythonclass Solution:
def solve(self, nums, target):
if sum(nums) < target:
return -1
if not nums:
return -1 if target != 0 else 0
l, r = 0, len(nums) - 1
result_len = float("inf")
cur_sum = 0
while l < len(nums) and r < len(nums):
cur_sum += nums[r]
if cur_sum == target:
result_len = min(result_len, r-l)
elif cur_sum > target:
# since this greater is caused by increasing r
# only shrinking l
while cur_sum > target:
l += 1
cur_sum -= nums[l]
if cur_sum == target:
result_len = min(result_len, r-l)
r += 1
return result_len
复杂度分析时间复杂度： O(N) |
思路滑动窗口+双指针 代码class Solution {
private:
bool fn(unordered_map<char,int>a,unordered_map<char,int>b){
for(auto x:b)
{
if(a[x.first]<x.second)
return false;
}
return true;
}
public:
string minWindow(string s, string t) {
int windowSize=t.size(),len=s.size();
if(t.size()>len)
return "";
unordered_map<char,int>a,b;
for(char c:t)
b[c]++;
int l=0,r=0,ansL=-1,ansLen=100001;
while(r<len)
{
while(r<len&&!fn(a,b)){
if(r==len)
break;
a[s[r]]++;
r++;
}
while(fn(a,b)){
a[s[l]]--;
l++;
}
if(r-l+1<ansLen){
ansL=l-1;
ansLen=r-l+1;
}
}
if (ansL == -1 || ansLen == 100001)
return "";
return s.substr(ansL, ansLen);
}
};
复杂度分析
|
思路
代码//双指针非固定滑动窗口
class Solution {
public int minOperations(int[] nums, int x) {
long sum = 0, res = Integer.MAX_VALUE;
for(int i: nums){
sum += i;
}
if(sum < x) return -1;
if(sum == x) return nums.length;
int left = 0, window = 0;
for(int i = 0;i < nums.length;i++){
window += nums[i];
while(window > sum - x){
window -= nums[left++];
}
if(window == sum - x) res = Math.min(res, nums.length - i - 1 + left);
}
return (int)res == Integer.MAX_VALUE?-1:(int)res;
}
}
//递归,backtrack
class Solution {
public int minOperations(int[] nums, int x) {
Deque<Integer> deq = new LinkedList<>();
long sum = 0;
for(int i: nums) {
deq.addLast(i);
sum += i;
}
if(sum < x) return -1;
int res = helper(deq, 0, x, nums.length);
return res == Integer.MAX_VALUE?-1:res;
}
public int helper(Deque<Integer> deq, int sum, int target, int length){
if(sum == target) return length - deq.size();
if(deq.size() == 0) return Integer.MAX_VALUE;
if(sum > target) return Integer.MAX_VALUE;
// System.out.println(sum);
int first = deq.pollFirst();
int l = helper(deq, sum+first, target, length);
deq.addFirst(first);
int last = deq.pollLast();
int r = helper(deq, sum+last, target, length);
deq.addLast(last);
return l<r?l:r;
}
}复杂度//2pointers //backtrack |
Number of Operations to Decrement Target to ZeroIntuition
Codeclass Solution {
solve(nums, target) {
if (target === 0) return 0;
const n = nums.length;
const totalSum = nums.reduce((acc, num) => acc + num, 0);
const remain = totalSum - target;
if (remain < 0) return -1; // impossible to reach target
if (remain === 0) return n; // need to remove all nums to reach target
let sum = 0;
let maxLen = -1;
let start = 0;
for (let i = 0; i < n; ++i) {
sum += nums[i];
while (sum >= remain) {
if (sum === remain) {
maxLen = Math.max(maxLen, i - start + 1);
}
sum -= nums[start++];
}
}
return maxLen === -1 ? -1 : n - maxLen;
}
}Complexity Analysis
|
|
public int solve(int[] nums, int target) { } |
|
思路： 代码： class Solution{ } 复杂度分析： |
思路删除和为 target 的若干数字等价于保留若干和为 sum(A) - target 的数。这样问题就转化为 求连续子数组和为 sum(A) - target 的最长子数组。这种问题可以使用滑动窗口来解决。 代码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复杂度分析
|
|
Number of Operations to Decrement Target to Zero Ideas
python代码 复杂度分析
|
|
class Solution: |
Number of Operations to Decrement Target to Zero思路
代码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复杂度分析
|
Note
Solutionclass Solution:
def solve(self, nums, target):
# find the longest subarray which sum equals sum(nums) - target
if not nums and not target:
return 0
target = sum(nums) - target
max_size = float('-inf')
l = win_sum = 0
for r in range(len(nums)):
win_sum += nums[r]
while l <= r and win_sum > target:
win_sum -= nums[l]
l += 1
if win_sum == target:
max_size = max(max_size, r - l + 1)
return len(nums) - max_size if max_size >= 0 else -1Time complexity: O(N) Space complexity: O(1) |
Number of Operations to Decrement Target to Zero思路滑动窗口数组各元素的和为 代码
int solve(vector<int>& nums, int target) {
typedef long long LL;
LL tot = 0;
for(auto cur: nums){
tot += cur;
}
if(tot < target) return -1;
if(tot == target) return nums.size();
LL sub_tot = tot - target;
LL cur_tot = 0;
int ii, jj;
int n = nums.size();
int ans = 0;
for(jj = 0, ii = 0; ii < n; ++ ii){
cur_tot += nums[ii];
while(jj < ii && cur_tot > sub_tot){
cur_tot -= nums[jj];
++ jj;
}
if(cur_tot == sub_tot){
ans = max(ans, ii - jj + 1);
}
}
if(ans == 0) return -1;
return n - ans;
}复杂度分析n为nums长度。
|
【Day 47】Number of Operations to Decrement Target to ZeroNumber of Operations to Decrement Target to Zero | binarysearch TaskYou are given a list of positive integers Return the minimum number of operations required to decrement Constraints
Example 1InputOutputExplanationWe can remove 思路一因为只允许我动头尾的元素，所以剩下的元素是一个连续子列，其和为：total - target 我们用一个滑动窗口去找到一个最长的连续子列，使得他们的和恰好是 total - target，即可 代码class Solution {
public int solve(int[] nums, int target) {
int numsSum = 0;
//get the total of the nums
for(int num : nums){
numsSum += num;
}
//get the target of the subString
int subStringTarget = numsSum - target;
if(subStringTarget == 0){
//it means all the element should be removed from the array
return nums.length;
}
if(subStringTarget < 0){
//it means the whole array can't meet the requirement
return -1;
}
//using sliding window
//The total of subString
int subStringSum = 0;
int maxLengthOfSubString = 0;
//close right and open right
for(int left = -1, right = 0; right < nums.length ; right ++){
//once the window is generated check the total of the window
subStringSum += nums[right];
//if left == right, the window is empty
while(left < right && subStringSum >= subStringTarget){
//move left point to narrow the window
if(subStringSum == subStringTarget){
//get the maxLength
maxLengthOfSubString = Math.max(maxLengthOfSubString, right - left);
}
left ++;
subStringSum -= nums[left];
}
}
return maxLengthOfSubString == 0 ? -1 : nums.length - maxLengthOfSubString;
}
}复杂度分析时间复杂度： O(n) 空间复杂度：O(1) |
int minOperations(vector<int>& nums, int x) {
int sum = 0;
for (int i = 0; i < nums.size(); ++i){
sum += nums[i];
}
if (sum < x){
return -1;
}
int left = 0, right = 0;
int sum2 = 0, res = INT_MAX;
while (right < nums.size()) {
sum2 += nums[right++];
while (sum2 > sum - x && left <= right) {
sum2 -= nums[left++];
}
if (sum2 == sum - x) {
res = (res > nums.size() - right + left - 1) ? nums.size() - right + left : res;
}
}
return res == INT_MAX ? -1 : res;
} |
思路问题可以转化成求一个连续的最大子数组，它的和等于sum(nums)-target，既然是求连续子数组，那自然就可以想到使用滑动窗口来解 代码class Solution {
public int solve(int[] nums, int target) {
if(target == 0)return 0;
if(nums.length==0)return -1;
int sum = 0;
for(int num : nums){
sum+=num;
}
int anchor = sum - target;
if(anchor<0)return -1;
int l = 0,r = 0,total =0,ans = Integer.MAX_VALUE;
while(r<nums.length){
total += nums[r];
while(total>anchor && l<=r){
total-=nums[l];
l++;
}
if(total == anchor){
ans = Math.min(ans,nums.length - r + l - 1);
}
r++;
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}
|
思路逆向思维。题目求从头尾删掉最少的元素使得他们的和为target。等价于，求一个最长连续子数组，使得和为 sum - target。 代码class Solution {
public int solve(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return target == 0 ? 0 : -1;
}
int sum = 0;
for (int n : nums) {
sum += n;
}
if (sum == target) return nums.length;
int newTarget = sum - target;
int start = 0;
int end = 0;
sum = 0;
int len = -1;
while (end < nums.length) {
sum += nums[end];
end++;
while (start < end && sum > newTarget) {
sum -= nums[start];
start++;
}
if (sum == newTarget) {
len = Math.max(len, end - start);
}
}
return len > 0 ? nums.length - len : len;
}
}复杂度时间：O(n) |
class Solution:
def solve(self, nums, target):
if not nums and not target:
return 0
target = sum(nums) - target
ans = len(nums) + 1
l = 0
total = 0
for r in range(len(nums)):
total += nums[r]
while l <= r and total > target:
total -= nums[l]
l += 1
if total == target:
ans = min(ans, len(nums) - (r - l + 1))
return -1 if ans == len(nums) + 1 else ans |
|
https://binarysearch.com/problems/Number-of-Operations-to-Decrement-Target-to-Zero
思路滑动窗口
Codeint solve(vector<int>& nums, int target) {
const int n = nums.size();
if(target == 0)
return 0;
if(n == 0 || (n == 1 && nums[0] < target))
return -1;
int sum = std::accumulate(nums.begin(), nums.end(), 0);
if(sum < target)
return -1;
target = sum - target;
int ans = n+1, ts = 0, j = 0;
for(int i = 0; i < n; ++i){
ts += nums[i];
while(i >= j && ts > target){
ts -= nums[j++];
}
if(ts == target)
ans = min(ans, n-(i-j+1));
}
return ans == n+1 ? -1 : ans;
}T: average: O(n) worst: O(n^2) 最坏的情况是nums右端是特别大的数，比如$nums=[1,1,1,1,100], target = 100$ |
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
suffixcnt = 0
for i in range(len(nums) - 1, -1, -1):
psum -= nums[i]
while psum + ssum < target:
ssum += nums[-1 - suffixcnt]
suffixcnt += 1
if psum + ssum == target:
ans = min(ans, i + suffixcnt)
if ans > len(nums):
ans = -1
return ans
|
思路打卡（参考官网） 代码`` 复杂度分析时间复杂度：O(n) 空间复杂度：O(1) |
|
刚开始理解错题意了，前后其实可以一起取，但是要保证前连续 && 后连续。 class Solution:
def solve(self, nums, target):
if target == 0: return 0
if sum(nums) < target: return -1
part = sum(nums) - target
l,r,temp = 0, 0, 0
res = float('inf')
for r in range(len(nums)):
temp += nums[r]
while temp > part:
temp -= nums[l]
l += 1
if temp == part:
res = min(res,(len(nums)-(r-l+1)))
return res if res != float('inf') else -1
Time complexity: O(N) |
【Day 47】Number of Operations to Decrement Target to Zero思路官方题解 代码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) |
思路双指针模拟滑窗 代码class Solution:
def solve(self, nums, target):
if not nums and not target:
return 0
target = sum(nums) - target
ans = len(nums) + 1
l = 0
total = 0
for r in range(len(nums)):
total += nums[r]
while l <= r and total > target:
total -= nums[l]
l += 1
if total == target:
ans = min(ans, len(nums) - (r - l + 1))
return -1 if ans == len(nums) + 1 else ans复杂度
|
思路题目可以转化为寻找最长的连续的数组,满足 nums所有元素的和sumAll - target 最后的结果就是数组的长度n - 满足条件最长的连续数组长度max import java.util.*;
class Solution {
public int solve(int[] nums, int target) {
if(target == 0){
return 0;
}
int n = nums.length;
int max = Integer.MIN_VALUE;
int sumAll = 0;
for(int num : nums){
sumAll += num;
}
int target2 = sumAll - target;
int j = 0, count = 0, sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
count++;
while (sum > target2 && j < n) {
sum -= nums[j++];
count--;
}
if (sum == target2) {
max = Math.max(max, count);
}
}
return max >= 0 ? n - max : -1;
}
} |
IntuitionChanging the way of thinking as "finding the longest subarray whose sum == sum(nums) - target" can convert this problem to a sliding window problem. Algorithm in python3Complexity Analysis:
|
class Solution {
public int solve(int[] nums, int target) {
if (target == 0) return 0;
int sum = 0;
for (int n : nums) sum += n;
if (sum == target) return nums.length;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int prefixSum = 0, targetSum = sum - target, maxLen = -1;
for (int i = 0; i < nums.length; i++){
prefixSum += nums[i];
if (map.containsKey(prefixSum - targetSum)){
maxLen = Math.max(maxLen, i - map.get(prefixSum - targetSum));
}
if (!map.containsKey(prefixSum)) map.put(prefixSum, i);
}
return maxLen == -1 ? -1 : nums.length - maxLen;
}
}Time Complexity: O(n), Space Complexity: O(n) |
思路其实就是求和 = sum - 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) {
if (winSum == sum - target) {
maxLen = Math.max(maxLen, right - left + 1);
}
winSum -= nums[left];
left++;
}
}
return maxLen == 0 ? -1 : nums.length - maxLen;
}
}复杂度分析TC: O(n) |
public int solve(int[] nums, int target) {
if (target == 0) return 0;
if (nums.length == 0) return -1;
int arrSum = 0;
for (int num : nums) {
arrSum += num;
}
// 目标数组的和
int subSumTarget = arrSum - target;
if (subSumTarget < 0) return -1;
int l = 0, r = 0, subSum = 0, opTimes = Integer.MAX_VALUE;
while (r < nums.length) {
subSum += nums[r];
while (subSum > subSumTarget && l <= r) {
// 如果超过了 扔掉左边
subSum -= nums[l];
l++;
}
if (subSum == subSumTarget) {
opTimes = Math.min(opTimes, nums.length - r + l - 1);
}
r++;
}
return opTimes == Integer.MAX_VALUE ? -1 : opTimes;
} |
思路
代码javascript class Solution {
solve(nums, target) {
if (target === 0) return 0
// 根据题意是要删除的元素和等于target
// 同时只能从前或者从后面删除元素
// 则中间部分是连续的，即sum - target的部分是连续的
// 这个连续的部分可以使用滑动窗口
const sum = nums.reduce((prev, cur) => prev + cur, 0)
const remain = sum - target
const len = nums.length
// 当剩余的数为0时，说明整个数组都要删除才能符合
if (remain === 0) return len
// 当剩余的数小于0，说明整个数组都要删除都不能符合
if (remain < 0) return -1
let left = 0
let right = 0
let minLen = Infinity
let count = 0
while (right < len) {
count += nums[right]
while (count > remain) {
count -= nums[left]
left++;
}
if (count === remain) {
minLen = Math.min(len - (right - left + 1), minLen)
}
right++
}
return minLen === Infinity ? -1 : minLen
}
}复杂度分析
|
|
补作业找到一个最大的滑动窗口 class Solution:
def solve(self, nums, target):
# sum(deleted nums) == 7
# sum(nums) -7 = sum(left nums)
if target == 0:
return 0
left = 0
newTarget = sum(nums)-target
curSum = 0
ans = -1
for right in range(len(nums)):
curSum+= nums[right]
if curSum == newTarget:
curLen = right-left+1
ans = max(ans, curLen)
elif curSum > newTarget:
while left <= right and curSum > newTarget:
curSum -= nums[left]
left+=1
if curSum == newTarget:
ans = max(ans, right-left+1)
if ans == -1:
return ans
return len(nums)-ans Time: O(n) |
思路
代码import java.util.*;
class Solution {
public int solve(int[] nums, int target) {
if(target==0)
return 0;
if(nums.length==0)
return -1;
int sum=0;
for(int i=0;i<nums.length;i++)
sum+=nums[i];
int newT=sum-target;
if(newT<0)
return -1;
int l=0,r=0;
int len=Integer.MIN_VALUE;
int tmpSum=0;
while(r<nums.length){
tmpSum+=nums[r];
while(tmpSum>newT&&l<=r){
tmpSum-=nums[l++];
}
if(tmpSum==newT){
len=Math.max(len,r-l+1);
}
r++;
}
return len<0?-1:nums.length-len;
}
}复杂度
|
|
int minOperations(vector& nums, int x) { } |
|
方法 实现语言: C++
int solve(vector<int>& nums, int target) {
int N = nums.size();
int newT = accumulate(nums.begin(), nums.end(), 0) - target;
if(newT == 0)
{
return N;
}
int sum = 0;
int maxlen = 0;
int left = 0;
for(int i = 0;i < N;i++)
{
sum += nums[i];
while(sum >= newT && i >= left)
{
if(sum == newT)
{
maxlen = max(maxlen, i - left +1);
}
sum -= nums[left];
left++;
}
}
return maxlen ==0 ? -1 : N - maxlen;
}复杂度分析 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
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.
The text was updated successfully, but these errors were encountered: