【LeetCode】209. Minimum length subarray

0 summary

• A problem can be implemented in many ways , The best is not necessarily the best . Some may be difficult to implement , Is worth learning .

---

1 subject

2 thought

2.1 The prefix and + Traverse

Use the prefix and to solve the problem , Double loop to find the minimal array that satisfies the meaning of the question , Complexity is O(nm), among m Is to satisfy the continuous and >=target Minimum sequence length of . This method （ My thoughts ） Compared with the latter two methods , It's really bad .

2.2 The prefix and + The sliding window

In fact, the best way to solve this problem is to use the sliding window method , Time complexity is the lowest .

2.3 The prefix and + Dichotomy

To be updated

3 Code

3.1

The following codes correspond to The prefix and + Traverse Thought

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        pre_sum = [0] * (len(nums)+1)        
        nums = [0] + nums #  There is one in front 0
        pre_sum[0] = nums[0]
        for i in range(1,len(nums)):
            pre_sum[i] = pre_sum[i-1] + nums[i]
            if target <= nums[i]:
                return 1
        
        if pre_sum[-1] < target:
            return 0
        elif pre_sum[-1] == target:
            return len(nums)-1
        else: 
            length = len(nums)
            for i in reversed(range(len(nums))):
                for j in reversed(range(0,i-1)): #  Find an interval 
                    if (j+length <= i): #  If the interval has exceeded  length, Is not the optimal solution 
                        break
                    # print(i,j,pre_sum[i] - pre_sum[j])
                    if pre_sum[i] - pre_sum[j] >=target:
                        length = min(length,i-j)
                        break
            return length