167. Two Sum II - Input Array Is Sorted

문제 링크 : https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

배열이 sorted 되어있을 때 , 배열의 합이 target과 같을 때 배열의 idx를 반환하는 문제이다.

처음에 배열을 일일이 더해봐야 하나 생각했지만 조금더 효율적으로 풀 수 있는 방법 중 하나로 투포인터를 이용하여 푸는 방법이 있았다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l , r = 0, len(numbers)-1
        
        while numbers[l] + numbers[r] != target:
            if numbers[l] +numbers[r] > target:
                r-=1
            else:
                l+=1
        return [l+1, r+1]

Runtime: 136 ms, faster than 87.51% of Python3 online submissions for Two Sum II - Input Array Is Sorted.
Memory Usage: 14.9 MB, less than 91.21% of Python3 online submissions for Two Sum II - Input Array Is Sorted.

2022.06.09
다시 한번 복습해보았다

이전에 풀었던 방법과 비슷한 방법으로 풀긴했는데
정렬되어있다는 점을 이용하여 풀었다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i ,j = 0, len(numbers)-1
        while i<j:
            if numbers[i]+numbers[j]>target:
                j-=1
            elif numbers[i]+numbers[j]<target:
                i+=1
            else:
                if numbers[i]+numbers[j]==target:
                    return i+1, j+1

맨 앞(가장 작은 숫자)과 맨 뒤(가장 큰 숫자)를 i,j로 두고 둘을 더했을 때 target보다 크면 숫자를 줄어야하므로 j을 그 앞으로 옮기고 , 작다면 더 큰 숫자라는 의미이므로 i를 그 다음으로 옮긴다.

그리고 해당 타겟과 같으면 인덱스를 반환한다.

Runtime: 210 ms, faster than 32.40% of Python3 online submissions for Two Sum II - Input Array Is Sorted.
Memory Usage: 14.9 MB, less than 89.05% of Python3 online submissions for Two Sum II - Input Array Is Sorted.

이전 방법보다 런타임이 더 오래걸렸다.