[Algorithm] LeetCode Twosum JavaScript hash table

Q. Twosum

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]

 

Solution 1. Brute Foce

이중 for문으로 해결 하였고, 문제에서 n^2안에 해결하면 된다고하여 문제는 없다.

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

 

Solution 2. Hash map

 

Data Structure(자료구조)를 사용하여 해결하는 방법이 흥미로워 정리해두려고 한다.

해시테이블과 해시충돌발생예시

1. Hash Table

• 자료구조의 종류 중의 하나
  
  • 배열(array) — 데이터들을 차례로 인덱스를 부여하며 순차적으로 나열
  • 리스트(list) — 데이터들을 서로 줄기로 엮어서 다음 데이터들을 연결
  • 해쉬(Hash, Dictionary) — 데이터의 기준값을 나름의 방법으로 분류해 정리
  • 트리(tree) — 데이터들을 몇 단계로 분류를 거치며 계층적으로 정돈
• key와 value를 가지는 자료구조 형태
• 데이터 순서 상관없이 특정 데이터를 빠르게 찾기 좋은 자료구조.
• 일상에서의 예로는 영어사전이 적절한 예.

2. Hash Function

• key와 연결되어 있는 value를 삽입, 삭제, 탐색하는 함수
• key가 들어오면 Random하게 주소값을 생성한 후, 해당 주소값에 key와 value를 저장
• 해시함수 과정에서 해시충돌 발생함 (비둘기집 원리)

3. Hash Table In JS

object가 대표적이며 ES6에서 map, set이 추가되었다. 

map 

• key(고유값), value로 이루어진 해쉬테이블
• get(탐색), set(삽입), delete(삭제), has(찾기),  size(크기), for of(반복문) >>> key, value 둘 중 골라서 출력이 가능하다.
• key type: number, string, function, object, NaN (string만 가능한 object와 차이.)

var human = new Map();
human.set('age', 20);

human.get('age'); //데이터 꺼내는 법
human.delete('age'); //데이터 삭제하는 법
human.size; //데이터 몇갠지 알려준다.

//Map 데이터 반복문 돌리기
for (var key of human.keys() ){
  console.log(key)
}

// 객체 인스턴스 생성 시 바로 key, value 부여해주는 법
var human = new Map([
  ['age', 20],
  ['name', 'hwang']
]);

 

hash map으로 해결한 코드

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

twoSum([1,2,3,4,8],9)

 

 

 

++etc

ES6 set으로 배열 중복 데이터 제거하기

var arr = [ 'hwang' , 'chaile', 'john', 'hwang' ];

var arrToSet = new Set(arr); //Array를 Set으로 바꿔준다.

arr = [...arrToSet]  //Set을 Array로 바꾸기

//output: [ 'hwang' , 'chaile', 'john' ];

 

참고:https://medium.com/happyprogrammer-in-jeju/%EA%B0%9C%EC%95%8C%EB%AA%BB%EC%9D%B8-%EB%8B%B9%EC%8B%A0%EC%9D%B4-%EC%9B%B9%EA%B0%9C%EB%B0%9C%EC%9D%84-%EC%8B%9C%EC%9E%91%ED%95%9C%EB%8B%A4%EB%A9%B4-4-61d43afbcb53