20.10.14 [Algorithm]

Toy Problem가 점점 건드리기가 힘들어지고 무서워진다. 어떻게 해결해야 할지.. 여러 알고리즘 문제를 많이 접해보면 좀 덜할까? 그래서 LeetCode 문제를 풀어보면서 감을 익혀보자!

1. 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.

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]

My Solution

Time Complexity : O(n^2)
Space Complexity : O(1)

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

조건문에서 nums[j]를 중첩 루프를 통해 찾는 방법이다.
Solution을 보니 내가 푼 해답이 Brute Force라는 알고리즘이라 한다.

Another Solution

const twoSum = function (nums, target) {
  const comp = {};
  for (let i = 0; i < nums.length; i++) {
    if (comp[nums[i]] >= 0) {
      return [comp[nums[i]], i]
    }
    comp[target - nums[i]] = i
  }
};

이런 접근 방법을 나도 생각할 수 있다면 좋겠다 ㅎㅎㅎ