[leetcode]Array - Two Sum

문제

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

---

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

풀이

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length-1; i++) {		// 1
        for (let j = i+1; j < nums.length; j++) {	// 2
            if (nums[i] + nums[j] === target) {		// 3
                return [i, j];
            }
        }
    }
};
twoSum([2,7,11,15], 9);

함수의 첫번째 인자: 배열, 두번째 인자: 목표값

시간 복잡도는 for 문이 중첩되어 있기 때문에 O(n²) 이다.

1. 첫번째 반복문으로 인덱스 i가  0 ~ 배열길이-1 미만 까지 순회하고,

2. 두번째 반복문으로 인덱스 j가 i+1 ~ 배열길이 미만 까지 순회하도록 한다.

3. num[i] + nums[j] 가 target 값이 되면 i와 j를 배열에 담아 리턴한다.

 

더 나은 풀이

// O(n) - One-pass Hash Table
var twoSum = function(nums, target) {
    let map = new Map;				// 1
    for (var i = 0; i < nums.length; i++) {	// 2
        let complement = target - nums[i];	// 2-1
        if (map.has(complement)) {		// 2-2
            return [map.get(complement), i]
        }
        map.set(nums[i], i);			// 2-3
    }
}
twoSum([11,15,2,7], 9);

코드풀이

1. Map 객체를 생성해서 변수에 담는다.

2. nums 배열을 반복 순회한다.

  2-1. target값에서 nums[i]값을 빼서 변수에 담는다.

  2-2. map 객체에 has메서드로 2-1의 변수값이 존재하는지 확인한다.

        가지고 있다면 map.get()으로 value값을 배열에 담고 i 값도 배열에 담아 리턴한다.

  2-3. map 객체에 set메서드로 key값은 nums[i], value값은 i로 담는다.

 

코드실행과정
map 객체에 key 값과 value 값이 차례로 쌓인다.
{
  11 : 0
  15 : 1
  2 : 2
}

i가 3일때 map 객체에 complement에 해당하는 값이 있으므로 true가 된다.
그러므로 complement에 해당하는 value값인 2와 i값인 3을 리턴한다.

complement(2) = target(9) - nums[i](7)
if (map.has(2)) return [map.get(2), i(3)] // [2, 3]