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

정수 배열 nums와 정수 대상이 주어지면 두 숫자의 인덱스를 반환하여 대상에 합산되도록 한다.
각 입력에 정확히 하나의 해답이 있다고 가정하고 동일한 요소를 두 번 사용하지 않을 수 있다. 어떤 순서로든 답변을 반환할 수 있다.
=> 배열 내의 두 요소의 합이 target인 두 요소의 index를 반환하시오.

 

Example

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: 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]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.(유효한 닶은 1개만 존재)

---

풀이

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

=> 반복문의 중복을 줄이기 위해 i는 배열의 길이 - 1 만큼 반복하고 j는 i보다 크도록 설정
     (nums[i] + num[j] 와 nums[j] + nums[i] 는 동일하기 때문)

 

• Runtime: 108ms ~ 175ms
• Memory: 39MB ~ 39.9MB

 

 

다른 사람 풀이

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    sumMap = {};
    // result = [];
    for(let i=0;i<nums.length;i++){
        let diff = target - nums[i];
        if(sumMap[diff] !== undefined) {
            return [sumMap[diff],i]; break;
        }else{
            sumMap[nums[i]] = i
        }
    }
    return result;
};

=> 반복문을 한번만 돌리고 매번 target에서 num[i]의 차이 값을 Map에 저장하여 결과값을 도출

 

---

결론

Map의 활용.. 대단하다