Two Sum

Two Sum

문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

처음 작성한 코드(완전 탐색)

var twoSum = function(nums, target) {
    const result = [];
    for(let i=0;i<nums.length;i++){
        for(let j=i+1; j<nums.length; j++){
            if (nums[i]+nums[j]===target){
                result.push(i);
                result.push(j);
                break;
            }
        }
    }
    return result;
};

풀이 및 해설

• 시간복잡도 → O(n) 혹은 O(nlogn)으로 풀어야함
• 내가 푼 코드는 완전 탐색(O(n^2)) → 데이터가 커지면 에러 발생할 수 있음
• (1) 정렬 알고리즘 (O(nlogn)) 이용 → 투 포인터 사용
  • 양 끝에서 더하면서 크기 비교하며 포인터를 이동
• (2) 해시테이블 (O(n))이용

---

정렬 알고리즘 이용한 Code

var twoSum = function(nums, target) {
    const result = [];
    notSortNum = [...nums]; // 기존 nums 배열 데이터 유지
    nums.sort(function (a,b) { return a-b; }); // nums 데이터 오름차순으로 정렬
    for(let i=0;i<nums.length;i++){
        const num = target-nums[i];
        if(nums.includes(num)){ // target-nums[i]의 값이 nums배열에 존재하는 경우
            let idx = notSortNum.indexOf(nums[i]); // 해당 값의 원본 인덱스 추출
            result.push(idx); // result 배열에 넣기
            delete notSortNum[idx]; // 같은 숫자 존재할 수 있으므로 result 배열에 넣은 원소 삭제(empty)
            result.push(notSortNum.indexOf(num));
            break;
        }
    }
    return result;
};

→ 포인트: 같은 숫자가 존재하는 경우 같은 인덱스 반환하므로 result 배열에 추가한 원소는 삭제(empty값으로 남김)

JS 문법

delete 연산자로 배열 항목 제거 → empty값으로 바뀜(배열 인덱스, length에 변화X)

delete 배열[인덱스]

const array = [1, 2, 3, 4, 5, 6];
delete array[4];
console.log(array);
// [1, 2, 3, 4, empty, 6]