Problem Description
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.
Key Insights
- The problem requires finding two distinct indices in an array that sum to a given target value.
- A brute-force approach would involve checking all pairs, which results in O(n^2) time complexity.
- An efficient approach uses a hash table to store indices of the numbers, allowing for O(n) time complexity.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
To solve the problem, we can use a hash table (or dictionary) to store the numbers we've seen so far along with their indices. As we iterate through the nums array, for each number, we can check if the complement (i.e., target - current number) exists in the hash table. If it does, we have found our two indices. Otherwise, we store the current number and its index in the hash table for future reference.