Two Sum II - Input Array Is Sorted - LeetCode

문제 접근 🤔

---

• 투포인터를 이용하여 탐색을 해보았다.

	이분 탐색	투포인터
시간복잡도	O(log n)	O(n)
방식	mid를 지정하여 탐색 범위를 절반으로 탐색	문제에서 주어진 조건을 맞추는 방향
양끝단 혹은 좌에서 우로 탐색
조건	데이터 정렬 sort 필요	필요 x, 있으면 좋음

• 이중 루프 대신 투포인터를 이용하면 시간 복잡도를 O(n^2) → O(n)으로 줄일 수 있다.
• 시작 인덱스를 start = 0, 끝 인덱스를 배열의 마지막 인덱스인 end = len(numbers) - 1 로 설정하자.
• 반복문을 돌며 numbers[start] + numbers[end] 와 target 을 비교하여 두 값을 더한 값이 타겟보다 크면 end의 위치를 왼쪽으로 보내주고, 작다면 start의 위치를 오른쪽으로 보내주며 탐색한다.
• 두 값이 서로 같아질 때 원하는 인덱스 값을 찾은 것이므로 탐색을 종료한다.
  
  
  

놓쳤던 부분 😅

---

• 없음
  
  
  

코드 😁

---

파이썬 코드(96 ms)

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

자바스크립트 코드(63 ms)

const twoSum = (numbers, target) => {
    let [start, end] = [0, numbers.length - 1];

    while (numbers[start] + numbers[end] !== target) {
        if (numbers[start] + numbers[end] > target) {
            end--;
        } else {
            start++;
        }
    }
    return [start + 1, end + 1];  
};