문제 설명
•
두 수를 더해 target이 되는 서로 다른 인덱스의 값 두 개를 찾아 그 인덱스를 반환하는 문제
예제 입력/출력
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Plain Text
복사
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Plain Text
복사
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Plain Text
복사
제약 조건
•
nums.length
•
nums[i]
•
target ≤
•
하나의 유효한 답변만 존재한다고 가정
문제 풀이
•
접근1 브루트 포스 -
◦
아이디어: 모든 쌍을 비교해서 target이 되는 경우를 찾는 방법
◦
특징: 간단하지만 느림
•
접근2 정렬 + 투 포인터 -
◦
아이디어:
▪
값 기준으로 정렬 후, 투 포인터로 합 비교
▪
인덱스를 유지하기 위해 [index, value] 형태로 변환
◦
특징: 인덱스 보존 필요
•
접근3 해시 테이블 -
◦
아이디어:
▪
현재 값과 target - 현재 값 (complement)의 존재 여부를 해시맵으로 체크
▪
존재하면 두 인덱스를 반환
◦
특징: 가장 효율적
풀이 코드
브루트 포스 - 33ms
정렬 + 투 포인터 - 7ms
해시 테이블 - 4ms
var twoSum = function (nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
// Return an empty array if no solution is found
return [];
};
JavaScript
복사
•
시간 복잡도: - 4ms
•
공간 복잡도: - 55.41MB