欢迎进入欧博网址(Allbet Gaming),欧博网址www.ALLbetgame.us开放会员注册、代理开户、电脑客户端下载、苹果安卓下载等业务。

首页科技正文

约搏单双游戏:209 | 长度最小的子数组

admin2022-07-278

约搏单双游戏www.eth108.vip)采用以太坊区块链高度哈希值作为统计数据,约搏单双游戏数据开源、公平、无任何作弊可能性。

写在前面~

最近朋友面试遇到了这道题

发来和小媛一起讨论的时候

突然觉得说这是一道虽然简单,但是仍然可以讨论一下的「medium」题目

决定发出来分享一下

这道题有比较容易想到的「O(n) 时间复杂度」的解法

但是难免有的面试官会"精益求精"

进阶的询问是否有「O(n log(n)) 时间复杂度」的解法

这就需要大家动动小脑瓜啦~(其实也不难想到)

闲话少说~

先来看题~

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足 其和 ≥ target 的 长度最小的 连续子数组

[nums_l, nums_l+1, ..., nums_r-1, nums_r] ,

并返回其长度。

如果不存在符合条件的子数组,返回 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

提示:

,

Usdt第三方支付平台

www.trc20.vip)是使用TRC-20协议的Usdt第三方支付平台,Usdt收款平台、Usdt自动充提平台。免费提供入金通道、Usdt钱包支付接口、Usdt自动充值接口、Usdt寄售回收。菜宝Usdt钱包一键生成Usdt钱包、一键调用API接口、一键出售Usdt。

,

1 <= target <= 109

1 <= nums.length <= 105

1 <= nums[i] <= 105

先停在这里

思考一会儿~

你会用什么方法呢

一、滑动窗口 / 双指针

思路:

· 定义两个指针 start 和 end 分别表示子数组(滑动窗口窗口)的开始位置和结束位置

· 维护变量 sum 存储子数组中的元素和

· 初始状态下,start 和 end 都指向下标 0,sum 的值为 0

· 每一轮迭代,将 nums[end] 加到 sum,如果 sum≥s,则更新子数组的最小长度,然后将 nums[start] 从 sum 中减去并将 start 右移,直到 sum<s,在此过程中同样更新子数组的最小长度

· 在每一轮迭代的最后,将 end 右移。

复杂度分析:

· 时间复杂度:O(n),其中 n 是数组的长度。指针 start 和 end 最多各移动 n 次。

· 空间复杂度:O(1)。c

二、前缀和 + 二分查找

思路:

· 因为这道题保证了数组中每个元素都为正,所以前缀和一定是递增的,这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正,这里就不能使用二分来查找这个位置了。

· 在确定每个子数组的开始下标后,找到长度最小的子数组需要 O(n) 的时间。

· 如果使用二分查找,则可以将时间优化到 O(logn)。

复杂度分析:

· 时间复杂度:O(nlogn),其中 n是数组的长度。需要遍历每个下标作为子数组的开始下标,遍历的时间复杂度是 O(n),对于每个开始下标,需要通过二分查找得到长度最小的子数组,二分查找得时间复杂度是 O(logn),因此总时间复杂度是 O(nlon)。

· 空间复杂度:O(n),其中 n 是数组的长度。额外创建数组 sums 存储前缀和。


       原文标题 : 209 | 长度最小的子数组

网友评论

热门标签