Source
https://leetcode.com/problems/two-sum/
Two Sum - LeetCode
Can you solve this real interview question? 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
leetcode.com
Code
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (let l = 0; l < nums.length - 1; l++) {
for (let r = l + 1; r < nums.length; r++) {
let left = nums[l];
let right = nums[r];
if (left + right === target) {
return [l, r];
}
}
}
};
How to solve?
for문을 두번 순회하면서 정답을 찾았다.
아무래도 더 좋은 방법이 있을 것 같아 다른 사람들의 코드를 보고 분석했다.
분석 코드 소스:
JavaScript w/ map - Time & Space O(N) - Two Sum - LeetCode
View AnikaErceg's solution of Two Sum on LeetCode, the world's largest programming community.
leetcode.com
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let mp = new Map()
// 1. map 함수 선언
for (let i = 0; i < nums.length; i++) {
// 2. for문으로 순회
let diff = target - nums[i]
// 3. target과 nums[i]차이인 diff를 정의한다.
if (mp.has(diff)) {
// 4. 만약 선언한 map 함수에 diff가 있다면
return [i, mp.get(diff)]
// i와 mp의 diff를 key로 하는 value 출력.
}
mp.set(nums[i], i)
// 5. mp에 nums[i] => i 형태의 hash맵 저장.
}
};
1. map()으로 hashmap을 선언하여 O(1)에 요소에 접근할 수 있도록 한다.
2. 하나의 for문으로 문제를 해결한다 (2중 for문 x)
3. for문의 매 순회마다 target과 nums[i]의 차이를 구한다.
4. 만약 선언한 map 함수에 diff(key)가 있다면 i와 mp의 key를 diff로 하는 value 출력.
5. 매 for문마다 hashmap에 key를 nums[i]로 value를 i로 하는 hashmap 저장.
'Problem solve' 카테고리의 다른 글
| [프로그래머스] 올바른 괄호 (Python) (2) | 2023.03.20 |
|---|---|
| [Leetcode] Letter Combinations of a Phone Number (Python) (0) | 2023.03.19 |
| [프로그래머스] 게임 맵 최단거리 (Python) (2) | 2023.03.14 |
| [프로그래머스] 하노이 탑 (Python) (0) | 2023.03.11 |
| [프로그래머스] 멀쩡한 사각형 (Python) (0) | 2023.02.06 |