[leetcode] 209. Minimum Size Subarray Sum

Description

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]Output: 2Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

分析

题目的意思是：求连续子数组只和等于s的最小长度。

定义两个指针left和right，分别记录子数组的左右的边界位置，然后我们让right向右移，直到子数组和大于等于给定值或者right达到数组末尾，此时我们更新最短距离，并且将left像右移一位，然后再sum中减去移去的值，然后重复上面的步骤，直到right到达末尾，且left到达临界位置，即要么到达边界，要么再往右移动，和就会小于给定值。

代码

class Solution {public: int minSubArrayLen(int s, vector& nums) { if(nums.empty()){ return 0; } int i=0; int j=i+1; int sum=nums[i]; int m=nums.size(); int len=m+1; while(j=s){ len=min(len,j-i); sum-=nums[i]; i++; } } return len==m+1 ? 0:len; }};

代码二 （python）

用了二分法来缩小空间，（腾讯面试被问到，当时觉得自己没写好，所以结束后重新写一下，发现效率没有双指针高）

class Solution: def minSubArrayLen(self, s: int, nums: List[int]) -> int: n=len(nums) sums=[0]*(n+1) for i in range(1,n+1): sums[i]=sums[i-1]+nums[i-1] min_len=float('inf') for i in range(0,n): l=i r=n-1 while(l<=r): mid=l+(r-l)//2 t=sums[mid+1]-sums[i] if(t

参考文献

​​[LeetCode] Minimum Size Subarray Sum 最短子数组之和​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。