[LeetCode] Two Sums

LeetCode - The World's Leading Online Programming Learning Platform

Two Sums:  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]
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]

 

---

내가 작성한 정답

function twoSum(nums: number[], target: number): number[] {
    let result = [];
    for (let now=0; now < nums.length - 1; now++) {
        for (let next=1; next < nums.length; next++) {
            if (nums[now] + nums[next] === target) {
                if (now !== next && !result.includes(now) && !result.includes(next)) {
                result.push(now, next)
                };
            }
        }
    }
    return result;
};

이중 반복문을 사용해 O(n^2)의 시간 복잡도로 풀었다. 

---

더 좋은 방법

HashTable을 이용한다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i

target에서 반복문에서 돌아가는 숫자를 뺀 값을 hashMap 상에 complement라는 key로, 인덱스는 value로 저장한다. 만약 complement가 이미 hashmap에 key 값으로 존재한다면 해당 complement에 해당하는 인덱스를 불러온다.(아마 여기서 배열의 순서는 중요하지 않은 듯하다.)

 

++ 깨알 자료구조 지식

hashmap이란? : https://velog.io/@taeha7b/datastructure-hashtable

[자료구조] Dictionary / HashMap / HashTable

 

HashTable(해시 테이블)은 Key 와 Value 의 쌍으로 데이터를 저장하는 자료구조다.
언어에 따라서 HashMap이라고도 불리며, 파이썬의 Dictionary 또한 HashTable로 구현되어 있다.

HashTable(HashMap, Dictionary)의 특징은 다음과 같다.

• 순차적으로 데이터를 저장하지 않는다.(non-iterable)
• Key를 통해서 Value값을 얻는다.
• Value값은 중복가능 하지만 Key는 중복될 수 없다.
• 수정 가능하다.(mutable)

파이썬의 List나 자바스크립트의 Array와 달리 저장된 데이터를 순차적으로 찾는게 아니고,
Key값을 통해서 Value값을 찾기 때문에 빠르다.