IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 和大于等于 target 的最短子数组 python解答 -> 正文阅读

[数据结构与算法]和大于等于 target 的最短子数组 python解答

题目描述:
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:
输入:target = 4, nums = [1,4,4]
输出:1

示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

解题思路1:
遍历数组nums, 遍历到第 i 个数, 那么右指针就从i+1开始计算, 如果sums[i:i+1]不大于等于target, 则右指针继续+1, 这种算法时间复杂度为O(n2), 在力扣上跑, 遇到很大的数组会超时.

def n2(nums, target):
	# 定义最短长度, 初始为0
    min_length = 0
    n = len(nums)
    for i in range(n):
    	# 右指针比i要大1
        m = i + 1
        while m <= n:
        	# 如果已知最短长度且比i到m的值还要小,那么就不用继续了
            if min_length and min_length <= m - i:
                break
            # 如果i到m的和大于等于target,则要得出min_length
            if sum(nums[i:m]) >= target:
                if min_length == 0:
                    min_length = m - i
                else:
                    min_length = min(min_length, m - i)
                break
            #右指针往右移动 
            m += 1
    return min_length

解题思路2:
作者:angela-x
链接:https://leetcode.cn/problems/2VG8Kg/solution/jian-zhi-offer-zhuan-xiang-tu-po-ban-shu-1epd/
来源:力扣(LeetCode)
1滑动窗口,有两个边界,一个左边界,一个右边界,开始的时候,左右边界都指向数组的首位置
2由于目标是找出大于或等于target的最短数组;用一个值来记录窗口内数字的和
如果两个指针之间的子数组中所有数字之和小于target,那么把右边界向右移动
3滑动窗口的总体思路是先移动右边界,让窗口中的值满足题目的解,也在是说在找到可行解的情况下
4再移动左边界,在可行解里面寻找最优解
根据大神给的思路, 我自己用python实现了, 时间复杂度为O(n), 代码如下

# 获取min_length的函数, 供on函数
def get_min_length(min_length, high, low):
    if min_length == 0:
        min_length = high - low
    else:
        min_length = min(min_length, high - low)
    return min_length


# 滑动窗口方法
def on(nums, target):
    # [2, 3, 1, 2, 4, 3]
    min_length = 0
    n = len(nums)  # 数组长度
    if n == 0:
        return min_length
    low, high = 0, 1
    while high - low >= 0 and high <= n:
        #print('sums is ', sum(nums[low:high]))
        if sum(nums[low:high]) >= target:
            min_length = get_min_length(min_length, high, low)
            if min_length == 1:
                return 1
            low += 1
        else:
            high += 1
    return min_length

在力扣上跑的得分如下:
在这里插入图片描述

如果对您有帮助, 麻烦您点个赞, 如果有问题或不同的想法欢迎交流, 一起进步

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-06-29 19:19:22  更:2022-06-29 19:22:28 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/28 20:23:43-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码