LeetCode Top Interview 150 - 167. Two Sum II - Input Array Is Sorted

🤔 문제 이해

비정렬된 배열에서 두개의 value을 더해 target값이 맞는 index값 두개 나오기

 

 

🤔 EX

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].

 

🤔 의사 코드 / 시간복잡도에 걸린코드

for문안에서 index =0부터 value를 가지고 계산후 indexOf로 나머지 값을 찾는다 
만약 -1이라면 다음 있다면 return으로 결과값 도출
예외상황발생 ex[0,0,3,4] target = 0 일때 index=1다음부터 찾아야하는데 1로 찾음 그래서 해결했지만 
O(n^2)라 또 안받아줌....

var twoSum = function(numbers, target) {
    numbers.sort((a,b)=>{a-b})

    for(let i=0;i<numbers.length;i++){
        if(numbers.indexOf(target - numbers[i],i+1)>0){
            return [i+1,numbers.indexOf(target - numbers[i],i+1)+1]
        }
    }
};

 

 

🤔 해결한 코드

시간 복잡도 때문에 또 실패한것을 보고(알고리즘 공부하자)

two pointer알고리즘이 생각났다 한 배열에서 두개의 값을 가지고 더하는 문제이기때문에 적용할수 있을것 같았다.

var twoSum = function(numbers, target) {
    numbers.sort((a,b)=>{a-b})
    let left =0
    let right = numbers.length-1

    while(left<right){
        let result = numbers[left] + numbers[right]

        if(result ==target){
            return [left+1,right+1]
        }else if(result>target){
            right --
        }else{
            left ++
        }
    }
};

 

🤔 다른 풀이방법

사실 two pointer알고리즘을 기반으로 풀었기 때문에 거의 같은 풀이 방법이 많았지만 

애초에 while문에서 조건을 주는 것도 좋은 생각 같았구

    while (numbers[p1] + numbers[p2] !== target)

 

 

왜 난 for문을 처음에 이용하면서 두개를 선언하여 사용할수 있다는 것을 잊고있었지... ㅋㅋㅋㅋㅋ

효율적인 방법이라고 생각된다

function twoSum(numbers, target) {
    for(let start = 0, end = numbers.length-1; start < end;){
        let sum = numbers[start] + numbers[end]
        if(sum === target)return [++start, ++end]
        else sum > target ? end-- : start++
    }
};

출처 : https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/discuss/520736/Concise-JavaScript-O(1)-Space-Solution