Two Sum
Description: Given an array of integers nums and a target value target, return the indices of two numbers in the array whose sum equals 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 = [3,4,5,6], target = 7
Output: [0,1]
Explanation: nums[0] + nums[1] = 3 + 4 = 7
Example 2:
Input: nums = [4,5,6], target = 10
Output: [0,2]
Explanation: nums[0] + nums[2] = 4 + 6 = 10
Constraints:
2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists
Recommended time and space complexity
You should aim for a solution with O(n) time complexity and O(n) space complexity, where n is the length of the nums array.
Hint 1
A brute force approach would be to use two nested loops to check all possible pairs of numbers. This would give O(n²) time complexity. Can you think of a more efficient solution?
Hint 2
For each number x, you are looking for another number y such that x + y = target. In other words, you are looking for complement = target - x. How can you quickly check if the complement exists in the array?
Hint 3
A hash table allows for O(1) lookups. You can store each visited number and its index in a hash table. For the current number, check if the complement exists in the table.