leetcode. Two Sum

문제 요약

정수 배열 nums 와 하나의 정수 target이 주어진다

nums의 수 중 두 개를 뽑아 더해서 target을 만들 수 있는 조합의 인덱스를 리턴하는 함수를 작성하라

하나의 답만 존재하며, 같은 인덱스의 수를 두번 사용하는 것은 불가능하다

풀이

var twoSum = function(nums, target) {
    for(let i=0; i<nums.length;i++){
        const diff = target - nums[i];
        for(let j=i+1; j<nums.length; j++){
            if(diff===nums[j]) return [i,j];
        }
    }
    return 'no answer';
};

첫 번째 문제답게 별다른 고민을 하지 않았다

리트코드는 처음 이용했는데 문제 해답에 대한 설명을 볼 수 있어서 정말 좋았다..

백준은 남의 코드 훔쳐보기 바쁘고, 프로그래머스는 댓글로 설명해주는 사람 없으면 설명은 없으니까..

여튼 그렇게 다른 정답을 보니 해시 테이블을 이용하길래 쭉 읽어봤는데 이런 경우에 쓰면 시간복잡도가 O(n)이되는 걸 알 수 있어서 나도 한번 구현해보기로 했다

풀이 2

let twoSum = function(nums, target) {
    const map = new Map()
    for(let i=0; i<nums.length;i++){
        map.set(nums[i],i);
    }
    for(let i=0; i<nums.length;i++) {
        const diff = target - nums[i];
        if (map.has(diff)&&map.get(diff)!==i) return [i,map.get(diff)];
    }
    return 'no answer';
};

처음 써보는 자료구조라 조금 생각했는데 key에는 index만 넣어야한다는 강박이 있어서 조금 헤맸다

key에 nums의 value를 넣어서 해결!

---

하지만 시간은 똑같았고 공간 복잡도만 늘어났다..

아마 테스트 케이스의 배열이 크지 않은가보다