A shop is running a promotion: a gift card can be spent on exactly two different items, and the card is only accepted if their prices add up to its value exactly. You are given the item prices as an integer array nums and the card value as target. Return the positions (indices) of the two items whose prices sum to target.
Each input has exactly one valid pair, and an item cannot be paired with itself. The two indices may be returned in either order.
Example:
Input: nums = [3, 9, 14, 5, 11], target = 16 Output: [3, 4] Why: nums[3] + nums[4] = 5 + 11 = 16. No other pair reaches 16.
The brute-force approach would be to use two nested loops to check every pair of numbers, which would be O(n²). We can do much better using a hash table (or a JavaScript Map).
- Create a hash map to store numbers we've seen and their indices.
- Iterate through the input array
nums. - For each number
num, calculate the required complement:complement = target - num. - Check if the
complementexists in our hash map.- If it does, we have found our pair. Return the index of the complement from the map and the index of the current number.
- If it doesn't, add the current number
numand its index to the hash map.
This approach has a time complexity of O(n) because we iterate through the array once, and each hash map lookup is O(1) on average. The space complexity is O(n) to store the hash map.
1 2 3 4 5 6 7 8 9 10 11