leetcode top interview 150 | Two Sum II - Input Array Is Sorted | Two Pointer

 

Question

 

오름차순으로 정렬되어있는 정수형 배열이 주어졌을때 선택한 두 정수의 합이 target number에 해당 할 경우,

index 위치를 담은 길이 2의 배열을 반환

 

동일한 요소를 두번 이상 사용할 수는 없는 One solution으로 구현  

 

Not Accepted Code - Time Limit Exceeded

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for(int i=0; i<numbers.length; i++){
            for(int j=i+1; j<numbers.length; j++){
                if(numbers[i] + numbers[j] == target) {
                    return new int[] {i+1, j+1};
                }    
            }
        }
        return null;
    }
}

numbers의 최대길이가 30000이기 때문에 O(N^2)인 현재 로직으로는 시간 초과가 일어난다.

 

Accepted Code

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        
        while(left<right){
            int sum = numbers[left] + numbers[right];
            if(sum == target){
                return new int[]{left + 1, right + 1};
            }else if(sum > target){
                right--;
            }else{
                left++;
            }
        }
        return null;
    }
}

 

Solve

 

Two Pointer : 투 포인터 알고리즘 
- 선형 구조에서 두개의 포인터를 움직여 가며 조건을 충족시키는 값을 찾을 때 활용
- O(N)의 시간복잡도 

 

numbers 배열이 이미 오름차순으로 정렬된 선형구조이기 때문에 투포인터 접근이 가능하다. 해당 로직으로 target number를 O(N)만에 찾을 수 있었다. 

 

left 인덱스를 배열의 시작 인덱스로, right 인덱스를 배열의 끝 인덱스로 설정하고 

twoSum 값을 구했을때 target보다 작으면 left 인덱스 값을 증가시키고 target보다 크면 right 인덱스 값을 감소시킨다. 

 

target number를 찾으면 1부터 시작하는 인덱스 값으로 조정한 후 배열을 생성해 리턴해준다. 

 

 

 

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150 

Two Sum II - Input Array Is Sorted - LeetCode