-
[LeetCode] TwoSum알고리즘 2019. 8. 30. 18:49
문제
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
Approach
O(n^2)에 답 찾으면 답 리턴
좀 빠르게 만들어보려고 원래 nums[i] + nums[j] == target 대신 target에서 nums[i]를 빼고
nums[j]가 빠진 값과 같으면 답 리턴하는걸로 해봄 -> 상위 38% 수행시간
Optimization
가장 빠른 방법은 target에서 nums[i] 뺀값을 hash 테이블 사용해 (c++에서 map) 저장해서 (hash[nums[i]] = i)
짝을 미리 찾아두고 iteration 마다 hash.find()를 통해 찾아지면 답 리턴
Code
https://github.com/chi3236/algorithm/blob/master/LeetCode_TwoSum.cpp
https://github.com/chi3236/algorithm/blob/master/LeetCode_TwoSumHash.cpp
'알고리즘' 카테고리의 다른 글
[LeetCode] Reverse Integer (0) 2019.09.07 [LeetCode] Longest Substring Without Repeating Characters (0) 2019.09.06 [LeetCode] Next Permutation (0) 2019.09.04 [LeetCode] Median of Two Sorted Array (0) 2019.09.02 [LeetCode] AddTwoNumbers (0) 2019.08.31