本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2024-11(2)

Number of Operations to Decrement Target to Zero - 滑动窗口

发布于2021-03-13 14:14     阅读(1452)     评论(0)     点赞(28)     收藏(3)


Number of Operations to Decrement Target to Zero - 滑动窗口

题目地址

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

题目描述

题目1
例子1

思路

题目要求去除数组nums的左右两端元素,并且去除的元素和为target,也就是留下中间的子数组,其和为sum(nums) - target;
题目还要求去除的元素个数越小越好,也就是留下的中间子数组的长度越大越好;
那么问题就转化为了找数组中间和为sum(nums) - target的最长子数组,令该和为我们的新目标new_target,步骤如下:

  1. 求出新目标new_target = sum(nums) - target,如果new_target == 0,也就是需要找到和为0的子数组,那就是把所有元素都去除了,返回数组长度n
  2. 接下来就是通过滑动窗口找子数组了,令左右指针指向滑动窗口的左右边界,从索引0开始滑窗
  3. right指针正常遍历数组,当滑动窗口内的和tmp_sum大于等于new_target的时候,开始缩紧左边界
  4. 如果tmp_sum正好与new_target相等,找到第一个符合要求的子数组,更新子数组最大长度max_len
  5. 左指针left右移,tmp_sum也相应的减小,当tmp_sum比new_target小或者left > right时循环结束,right继续遍历
  6. 最后返回去除的元素个数 n - max_len,如果max_len为0,说明没有找到符合要求的子数组,返回 - 1

代码(Python)

class Solution:
    def solve(self, nums, target):
        new_target = sum(nums) - target
        if new_target == 0:
            return len(nums)
        tmp_sum = 0
        max_len = 0
        left = 0
        for right, num in enumerate(nums):
            tmp_sum += num
            while tmp_sum >= new_target and left <= right:
                if tmp_sum == new_target:
                    max_len = max(max_len, right - left + 1)
                tmp_sum -= nums[left]
                left += 1
        return len(nums) - max_len if max_len else -1

代码(Java)

import java.util.*;

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

复杂度分析

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

原文链接:https://blog.csdn.net/qq_41726606/article/details/114663700



所属网站分类: 技术文章 > 博客

作者:Hdhhd

链接:http://www.javaheidong.com/blog/article/114437/dfc71d77b9829575f1bf/

来源:java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

28 0
收藏该文
已收藏

评论内容:(最多支持255个字符)