LeetCode - Two Sum [난이도 : Easy]

문제 설명

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.

입출력 예시

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 <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Solution#1 : Brute force

• 직관적으로 for문을 중첩해서 모든 가능한 케이스를 검토해봄(가능한 케이스를 찾기전까지)

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

문제는 해결하였지만 TC가 좋지 않아 Leetcode의 솔루션을 참고했다.

To improve our run time complexity, we need a more efficient way to check if the complement exists in the array

Solution#2 : Map

• 모든 조합을 확인해볼 필요 없음
• targer - nums[i] 값이 배열에 존재하는지를 확인 => 해쉬 사용
  - for문을 돌면서,
  - i번째에 'targer - nums[i]'값을 key로 가진 element가 있는지 map에서 확인
  • 값이 있으면 조합을 리턴
  • 값이 없으면 nums[i]를 해쉬의 key로, i는 value로 저장

let SumWtHash = function(nums, target) {
    
    let i;
    let j;

    let map=new Map()
    
    for(i=0; i<nums.length; i++){
      needNum=target-nums[i];
      let getIdx=map.get(needNum);
      if(getIdx!=undefined){
          return [getIdx,i]
      }
      map.set(nums[i],i);
    }
};

속도가 빨라졌다 ^^

첫번째 과제 해결 ~.~