LintCode 406 · Minimum Size Subarray Sum | 和大于S的最小子数组

题目

406 · 和大于S的最小子数组

暴力解法

枚举子数组 = 枚举起点与终点
对于每个找到的子数组，遍历并求和
更新最短的、满足要求的子数组即可

时间复杂度 O(n ^ 3)，空间复杂度 O(1)

# python3
class Solution:
    """
    @param nums: an array of integers
    @param s: An integer
    @return: an integer representing the minimum size of subarray
    """
    def minimumSize(self, nums, s):
        # write your code here
        min_length = float("inf")
        for start in range(len(nums)):
            for end in range(start,len(nums)):
                sum_of_subarray = 0
                for i in range(start,end + 1):
                    sum_of_subarray += nums[i]
                if sum_of_subarray >= s:
                    min_length = min(min_length,end-start+1)
        if min_length == float("inf"):
            return -1
        
        return min_length

# Time Limit Exceeded

前缀和优化

首先使用 O(n) 的时间获得前缀和数组
然后O(n ^ 2)枚举起点终点，同时借助前缀和计算子数组和
子数组和 >= s ：更新子数组的长度

总时间复杂度 O(n + n ^ 2) = O(n ^ 2)
空间复杂度 O(n)

# python3
class Solution:
    """
    @param nums: an array of integers
    @param s: An integer
    @return: an integer representing the minimum size of subarray
    """
    def minimumSize(self, nums, s):
        # write your code here
        # n = len(nums)
        prefix_sum = self.get_prefix_sum(nums)
        min_length = float("inf")
        for start in range(len(nums)):
            for end in range(start,len(nums)):
                if prefix_sum[end + 1] - prefix_sum[start] >= s:
                    min_length = min(min_length,end - start + 1)

        if min_length == float("inf"):
            return -1
        
        return min_length

    def get_prefix_sum(self,nums):
        prefix_sum = [0]
        for i in range(1,len(nums) + 1):
            prefix_sum.append(prefix_sum[i - 1] + nums[i - 1])
        
        return prefix_sum

二分

对于每个下标 i ，都让他作为子数组左边界
使用二分法找出子数组最靠左的右边界
使用前缀和求出子数组之和，与s比较并更新答案

总时间复杂度：O(n * logn) = 枚举起点位置：O(n) + 二分终点位置：O(logn)
总空间复杂度：O(n)

# python3
class Solution:
    """
    @param nums: an array of integers
    @param s: An integer
    @return: an integer representing the minimum size of subarray
    """
    def minimumSize(self, nums, s):
        # write your code here
        # n = len(nums)
        prefix_sum = self.get_prefix_sum(nums)
        min_length = float("inf")
        for start in range(len(nums)):
            end = self.get_end_of_subarray(prefix_sum, start, s)
                if prefix_sum[end + 1] - prefix_sum[start] >= s:
                    min_length = min(min_length,end - start + 1)

        if min_length == float("inf"):
            return -1
        
        return min_length

    def get_prefix_sum(self,nums):
        prefix_sum = [0]
        for i in range(1,len(nums) + 1):
            prefix_sum.append(prefix_sum[i - 1] + nums[i - 1])
        
        return prefix_sum

    def get_end_of_subarray(self,prefix_sum,start,s):
        left,right = start,len(prefix_sum)-2
        while left + 1 < right:
            mid = left + (right - left) // 2
            if prefix_sum[mid + 1] - prefix_sum[start] >= s:
                right = mid
            else:
                left = mid

        if prefix_sum[left + 1] - prefix_sum[start] >= s:
            return left
        return right

同向双指针

遍历每一个左指针 i
找到满足 sum(a[i],…,a[j]) >= s 的右指针 j
更新最短的子数组长度

时间复杂度为 O(2 * n) = O(n)
空间复杂度 O(1)

模板

j = 0 or j=1
for i from 0 to (n-1)
    while j < n and (i,j的搭配不满足条件)
        j += 1
    if (i,j的搭配不满足条件)
        处理i,j的这次搭配

class Solution:
    """
    @param nums: an array of integers
    @param s: An integer
    @return: an integer representing the minimum size of subarray
    """
    def minimumSize(self, nums, s):
        # write your code here
        n = len(nums)
        min_length = float("inf")
        sum_of_subarray = 0
        j = 0
        for i in range(n):
            while j < n and sum_of_subarray < s:
                sum_of_subarray += nums[j]
                j += 1
            if sum_of_subarray >= s:
                min_length = min(min_length,j - i)
            sum_of_subarray -= nums[i]

        if min_length == float("inf"):
            return -1
        return min_length

备注

哪些是“连续”的

• 子串 (substring) – 连续
• 子数组 (subarray) – 连续
• 子序列 (subsequence) – 不连续

遇到subarray的解题技巧

• prefixSum
• 同向双指针

所有的双指针解法时间复杂度都是O(n)