[leetcode] 1. Two Sum

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]
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]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

 

Follow-up: 

Can you come up with an algorithm that is less than O(n2) time complexity?

 

풀이 - 1

function twoSum(nums: number[], target: number): number[] {
  let result: number[] = [];

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (i === j) {
        continue;
      }

      if (nums[i] + nums[j] === target) {
        result.push(i, j);
      }
    }
  }

  return result;
}

더 좋은 코드를 만들수도 있었지만 O(n^2)보다 단축된 코드를 만들수 있는지 물어보는 문구가 보여서 비교를 해보고싶어 일단 중첩반복문으로 구현해보았다.

 

.... hash table을 사용하라는 힌트를 들었음에도 그럴듯한 구상이 떠오르지 않아 나중으로 미뤄두어야겠다.. ㅜㅜ