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:
Example 2:
Example 3:
Constraints:
Use HashTable to record the index of each number and calculate the difference between the target and current number, then check whether the difference is in HashTable or not, if so, the answer is found.
Target = 9, Numbers = [2, 7, 11, 15], Table = []
All of the differences:
We can found the answer is [0, 1].
We need to allocate a new array to store the index of numbers, then sort the indices via number, and use binary search to find out the answer.
Target = 9, Numbers = [7, 11, 2, 15].
The source code:
See the full solution.
leetcode
Easy
Array
Hash Table
Sort
Binary Search