LeetCode - Minimum Size Subarray Sum-CodePudding

[Minimum Size Subarray Sum][1]

The leetcode question is given an array of n positive integers and a positive integer t, find the minimal length of a contiguous subarray such that the sum ≥ t. If there isn't one, return 0 instead.

The following is my code.

class Solution(object):
def minSubArrayLen(self, target, nums):
    """
    :type target: int
    :type nums: List[int]
    :rtype: int
    """
    start_idx = 0
    end_idx = 0
    min_len = float('inf')

    while end_idx < len(nums):
        if sum(nums[start_idx:end_idx   1]) < target:
            end_idx  = 1
        else:
            min_len = min(end_idx - start_idx   1, min_len)
            start_idx  = 1
    return 0 if min_len == float('inf') else min_len

My code did not pass the following test case, and the error is Time Limit Exceeds

396893380
[3571,9780,8138,1030,2959,6988,2983,9220,6800,7669,2528,3994,6090,311,5683,9232,9698,1784,6543,4018,1340,3170,5097,9876,8881,6303,7964,2469,1119,9259,9429,9355,9904,2971,6240,3973,4972,1874,7037,4631,4666,7809,6878,5656,7227,1833,4772,8200,9594,9250,1881,4811,2669,7077,7531,8497,3821,5741,7488,2521,469,6108,431,3985,1641,8732,398,9934,4785,5061,4882,4819,9986,3317,2683,7800,9887,7277,5145,9537,7089,1467,5458,1598,3083,2867,9046,6089,2657,1107,2110,9020,7771,4928,848,896,558,6416,5128,9534,5410,2349,3430,4081,5996,9447,420,3514,6814,9873,1486,4576,6161,...]

My code only works fine on small array and will take a lot of time if the array is large. The problem might be sum(nums[start_idx:end_idx 1]) because this is very inefficient in Python. But I do not know exactly what the problem is with my code and why.

Could anyone help me with this? Thank you!

[1] https://leetcode.com/problems/minimum-size-subarray-sum/

CodePudding user response：

Yes, sum(nums[start_idx:end_idx 1]) is insufficient. It recalculate the sum from start_idx to end_idx, and it is called len(nums) times. Instead, we can use a variable sub_sum to store the sum of subarray. Then we just need to do the add/subtract operations on sub_sum, and don't need to call sum() function.

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        start_idx = 0
        end_idx = 0
        min_len = float('inf')
        sub_sum = 0

        while end_idx < len(nums):
            sub_sum  = nums[end_idx]
            if sub_sum >= target:
                while (sub_sum - nums[start_idx] >= target):
                    sub_sum -= nums[start_idx]
                    start_idx  = 1
                min_len = min(end_idx - start_idx   1, min_len)
            end_idx  = 1

        return 0 if min_len == float('inf') else min_len