# [Leetcode]167. Two Sum II - Input Array Is Sorted

limelimejiwon·2022년 3월 11일
0

목록 보기
8/67

## 📄 Description

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] _of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

### Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

### Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

### Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

## 🔨 My Solution

• numbers array is sorted. We can use this condition.
• use two pointers for left(start) and right(end)
- numbers[left] is the smallest number in the array
• numbers[right] is the biggest number in the array
• check numbers[left]+numbers[right]
(1) if check == target, return the index of left&right
(2) if check<target, since it is smaller than the target, move left pointer to the next index.
(3) if check>target, since it is bigger than the target, move right pointer to the previous index.

## 💻 My Submission

class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left=0
right=len(numbers)-1

while left<right:
check=numbers[left]+numbers[right]
if check==target:
return [left+1,right+1]
elif check<target:
left+=1
else:
right-=1

## 🔎 Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Runtime: 276 ms
Memory: 14.8 MB

## ❓ How Can I improve it?

• using Binary Search Method?
- Since Binary Search is available and efficient for sorted array, so we can try solving this problem with using Binary search.