[LeetCode 167] Two Sum II - Input Array Is Sorted

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

Two Sum II - Input Array Is Sorted - LeetCode

Think

정렬된 배열과 타겟 수가 주어지고, 배열에서 어떤 두 수를 더해야 타겟 수를 만들 수 있는지 두 수의 인덱스를 구하는 문제

주의할 점은 인덱스를 1부터 시작하는 것으로 셀 것.

 

주어지는 배열이 정렬되어 있으므로 투 포인터 기법으로 풀이가 가능하다

(정렬되어있지 않으면 투 포인터로는 못 푼다)

 

 

 

 

Solution

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        #포인터 두 개를 양끝에 위치시킴
        left = 0
        right = len(numbers) -1
        
        #탐색 시작
        while not left == right : #두 포인터가 만나면 답이 없는 것
            #현태 위치의 두 값의 합과 target값 비교하며 포인터 이동시킴
            if(numbers[left] + numbers[right] < target) :
                left += 1
            elif(numbers[right] + numbers[left] > target) :
                right -= 1
            else : # 합이 target 값임
                return left+1, right+1 #배열의 인덱스를 1부터 세는 걸로 풀이하도록 했으므로

 

 

 

Get