LeetCode 209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a 

subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

 

 

#풀이

 

그림으로 그려서 각 인덱스를 포인터가 증가 될 떄마다 2중 for문을 통해 중복되는 값을 제외하고 계산한값을 모두 탐색하는 방법을 생각했다.

 

하지만 .....

 

class Solution(object):
    def minSubArrayLen(self, target, nums):
        min_range=1e9
        for i in range(len(nums)):  #인덱스
            for ii in range(i,-1,-1):
                if target ==sum(nums[-(ii+1):]):
                    min_range= min(min_range,ii+1)
        if min_range == 1e9:
            min_n
            
        return min_range

틀렸다고 나오는 테스트케이스

1,2,3,4,5 중 3개의 번호를 뽑아서 11을 만들어야한다는데.. 연속된 수로 나오는 값으로는 만들 수 없는 값인데 어떻게..?

 왜 안되지라고 고민하던 중.. 문제에서 target의 값과 같은게 아니라 동일하거나 큰 값을 만들 수 있는 경우를 찾는거였다

문제를 잘 읽어야지 ㅠㅠ 

 

결론은 뒤에서부터 슬라이싱해서 자르는 방법이라 중간에 나오는 두가지 값을 더해주지는 못했다 결국 

포인터를 만든 후 포인터를 움직여서 값을 찾는 방식으로 바꿨다.

 

 

 left 포인터를 사용해서 right 포인터를 두고 작다면  왼쪽포인터의 값을 +1 증가시키고 , while문을 통해 값의 조건식 (크거나 같음)을 만족시키면 멈추고  만족시키지 못한다면 left 포인터가 오른쪽으로 움직이며 값을 증가시키게 된다,

class Solution(object):
    def minSubArrayLen(self,s, nums):
        min_range=1e9
        left =0
        temp = 0
        
        for i in range(len(nums)):
            temp += nums[i]
            while temp >= s:
                min_range = min(min_range, i - left + 1)
                temp -= nums[left]
                left += 1
        if min_range == 1e9:
            min_range= 0

        return min_range

 

 

문제를 잘 읽자 ...!  ㅠㅠ