0209-leetcode算法实现之长度最小子数组-minimum-size-subarray-sum-python&golang实现
2021/10/16 9:09:44
本文主要是介绍0209-leetcode算法实现之长度最小子数组-minimum-size-subarray-sum-python&golang实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给定一个含有 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
进阶:
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-size-subarray-sum
python
# 长度最小的子数组 # 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 class Solution: def minSubArrayLen(self, nums: [int], target: int) -> int: """ 滑动窗口,时间O(n), 空间O(1) 思路: 1.初始化求和sum,返回结果res,左边界index=0 2.移动右边界,sum累加计和 3.当sum < target,不断累加计和,重复步骤2 4.当sum >= target,考虑移动左边界,减小sum值,res取上步res及序列长度i-index+1的较小值 5.重复步骤4,直到sum < target,重复步骤3 6.遍历结束后,取到的res即为满足target计和的子序列长度最小的数组长度 :param nums: :param target: :return: """ res = float('inf') sum = 0 index = 0 for i in range(len(nums)): # 窗口右边界,不断右移 sum += nums[i] # 累加计和 while sum >= target: res = min(res, i-index+1) # 取长度小值,因为 sum >= target sum -= nums[index] # 窗口左边界右移,sum减小, 左边界index右移 index += 1 return 0 if res == float('inf') else res def minSubArrayLen1(self, nums: [int], target: int) -> int: """ 暴力法, 时间O(n^2), 空间O(1) 思路: 1.初始化变量,即序列长度 2.从数组的第一个元素i开始,从该元素取j往后遍历,依次累加计和,每次初始化sum为0 3.如果sum大于等于target,此时记录其连续序列长度即j-i+1 4.res即序列长度和sublen比较,取小值,跳出该次遍历 5.重复2、3、4,直至遍历完所有元素,此时的res就是序列最小的符合条件的长度 :param nums: :param target: :return: """ INT_MAX = 2**31 - 1 res = INT_MAX # 初始化res, 最终结果变量 for i in range(len(nums)): # 子序列起点i sum = 0 # 每次更新其实位置时,置零 for j in range(i, len(nums)): # 设置子序列的终止位置j sum += nums[j] # 逐次累加 if sum >= target: # 子序列和超过target,更新res sublen = j - i + 1 # 子序列长度 res = res if res < sublen else sublen # 保持最小的res break # 小者,条件最短的子序列 return 0 if res == INT_MAX else res # res没有更新,则返回0 if __name__ == "__main__": nums = [1,2,3,5,2,1,1,4,1] target = 9 target1 = 50 test = Solution() print(test.minSubArrayLen(nums,target)) print(test.minSubArrayLen1(nums,target1))
golang
package main import ( "fmt" ) func main() { nums := []int{1, 2, 3, 5, 2, 1, 1, 4, 1} target := 9 fmt.Println(minSubArrayLen(target, nums)) } // 滑动窗口-时间O(n) func minSubArrayLen(target int, nums []int) int { const INT_MAX = int(^uint(0) >> 1) var res int = INT_MAX var sum int var index int = 0 for i := 0; i < len(nums); i++ { sum = sum + nums[i] for sum >= target { if res < i-index+1 { res = res } else { res = i - index + 1 } sum = sum - nums[index] index++ } } if res == INT_MAX { return 0 } else { return res } } // 暴力法-时间O(n^2) func minSubArrayLen1(target int, nums []int) int { const INT_MAX = int(^uint(0) >> 1) var res int = INT_MAX var sum int var sublen int for i := 0; i < len(nums); i++ { sum = 0 for j := i; j < len(nums); j++ { sum = sum + nums[j] if sum >= target { sublen = j - i + 1 if res < sublen { res = res } else { res = sublen } break } } } if res == INT_MAX { return 0 } else { return res } }
这篇关于0209-leetcode算法实现之长度最小子数组-minimum-size-subarray-sum-python&golang实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-26Python基础编程
- 2024-11-25Python编程基础:变量与类型
- 2024-11-25Python编程基础与实践
- 2024-11-24Python编程基础详解
- 2024-11-21Python编程基础教程
- 2024-11-20Python编程基础与实践
- 2024-11-20Python编程基础与高级应用
- 2024-11-19Python 基础编程教程
- 2024-11-19Python基础入门教程
- 2024-11-17在FastAPI项目中添加一个生产级别的数据库——本地环境搭建指南