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: 2
Explanation: 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).

描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例:

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

思路

使用两个指针left和right，用_sum来表示当前的和. right不断向右移动，_sum累加，当_sum大于等于s的时候，left向右移动直到_sum小于s，有效长度为right-left+2,返回所有有效长度的最小值即可.

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-01-22 11:37:16
# @Last Modified by:   何睿
# @Last Modified time: 2019-01-22 11:37:16

import sys


class Solution:
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        # 初始化长度
        length = sys.maxsize
        _sum, left, right = 0, 0, 0
        while right < len(nums):
            _sum += nums[right]
            # 如果当前的和已经大于等于s
            if _sum >= s:
                # 我们将左指针向右移动，和小于s时跳出
                while _sum >= s and left <= right:
                    _sum -= nums[left]
                    left += 1
                # 更新长度
                length = min(right - left + 2, length)
            right += 1
        # 如果length始终没有发生改变返回0，否则返回length本身
        return length if length != sys.maxsize else 0