Today's Challenge

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Two Sum II - Input Array Is Sorted - LeetCode

간단하게 풀 줄 알았던 문제인데 TL 발생.
원인을 찾아보니, 접근 방식이 조금 틀렸음.

최근에 회사 사람들과 문제풀이 스터디에서 풀어봤던 Two Pointer 방식으로 풀어야 함.
그렇지 않으면 TL이 발생할 수밖에..

다음부터 for statement의 횟수가 커진다 싶으면 Two Pointer를 생각해봐야겠다.

# TIME LIMIT EXCEEDED
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l = len(numbers)
        for i in range(l-1):
            for j in range(i+1, l):
                if numbers[i] + numbers[j] == target:
                    return [i+1, j+1]
                if numbers[i] + numbers[j] > target:
                    break

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