Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the 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 :
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Solution :
#include <iostream>#include <unordered_map>#include <vector>std::vector<int> twoSum(std::vector<int>& nums, int target) { std::unordered_map<int, int> numIndexMap; for (int i = 0; i < nums.size(); ++i) { int complement = target - nums[i]; if (numIndexMap.find(complement) != numIndexMap.end()) { return {numIndexMap[complement], i}; } numIndexMap[nums[i]] = i; } // It's guaranteed that there is exactly one solution, so this return is just to avoid compilation warnings. return {};}int main() { std::vector<int> nums = {2, 7, 11, 15}; int target = 9; std::vector<int> result = twoSum(nums, target); std::cout << "Output: [" << result[0] << ", " << result[1] << "]" << std::endl; return 0;}
Complexity :
Time complexity: O(n)
Space complexity: O(n)
Explanation:
The solution uses a hash map to store the indices of the elements as they are traversed. For each element, it calculates the complement needed to reach the target. If the complement is already in the hash map, it means we have found a pair whose sum is equal to the target.