[알고리즘 - LeetCode] Two Sum

문제

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

정수 배열로 이루어진 배열과 정수 값 하나가 두 개의 인자로 주어지며, 첫 번째 인자의 정수들 중 두 값 더했을 때 두 번째 인자 값이 되는 배열 인덱스를 리턴하라.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

풀이

제출 코드

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

1. 배열을 두 번 순회하며 정수를 값을 더해서 target 값과 비교하여 리턴시켰고
2. 같은 인덱스 값을 리턴하면 안되기 때문에 i !== j 조건을 &&연산자로 추가하였다.

버블 정렬과 비슷한 느낌으로 '비효율적인' 시간복잡도를 가진다^^;

타 제출 코드와 실행 속도 비교

코드워즈와 달리 리트코드는 다른 사용자들의 코드 실행 속도와 비교 데이터가 나와서 좋다. 제출 코드가 두 번 순회를 돌아서 비효율적이라고 생각하기는 했지만 이렇게 시각적으로 확인하고나니 개선해야할 필요성을 더 느끼게 됨.

시간 복잡도

시간 복잡도 O(n)2

개선 방안

const twoSum = function(nums, target) {
    const valsMap = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
      
        if (valsMap.get(complement) !== undefined) {
          return ([valsMap.get(complement), i])
        } else {
          valsMap.set(nums[i], i)
        }
    }
    
};

다른 제출 살펴보니 속도가 높은 코드들은 대체로 new Map를 사용한 것을 발견할 수 있었다.
1. 배열을 순회하면서 target에서 배열의 정수 값을 빼서 찾아야 하는 나머지 값을 complement에 상수로 정해두고
2. 해당 값이 valsMap객체에 있는지 확인하여
3. 없는 경우 할당하고
4. 있는 경우에는 해당 인덱스와 현재 순회중인 인덱스를 리턴한다.

참고

new Map

생성자 Map 객체는 키-값과 입력 순서를 저장시킨다.
.delete, .clear, .has, .set, .get메소드등의 사용하여 객체 값을 삭제, 확인, 할당하거나 불러올 수 있다.

Map과 Object

1. 원시 값으로 제한된 Object와 Map은 함수, 객체까지 키 값으로 사용할 수 있다.
2. Object와 달리 Map의 키는 추가된 순서대로 정렬되므로 순회시 삽입 순서가 필요한 경우라면Map을 사용하는 것이 좋다.

참고 mdn Map