Algorithm | Two Sum

본 글은 leetCode의 Two Sum 문제 솔루션을 JavaScript 코드로 정리한 글입니다.

Approach #1: Brute Force

모든 경우의 수를 확인하여 답을 찾는 방법입니다.

이중 반복문으로 두 원소의 합을 구합니다.

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

시간복잡도

O(n²)

Approach #2: Hash Table

객체를 hash table처럼 사용하여 더 효율적으로 해결하는 방법입니다.

객체의 key에 배열의 원소 값을, value에 target과 원소 값의 차를 저장합니다.

var twoSum = function(nums, target) {
  let hash = {};
  for(let i in nums) {
    if(hash[target - nums[i]]) return [i, hash[target - nums[i]]];
    hash[nums[i]] = i;
  }
};

시간복잡도

O(n)

References

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

Back to top ↑