Problem Statement
Given an integer array of size N, return indices of the two numbers such that they add up to a specific target.
Function Signature:
C++
vector<int> twoSum(vector<int> input, int target) {...}
Inputs:
input = [2, 4, 6, 7]
target = 9,
Outputs:
[0, 3]
(because input[0] + input[3] = 2 + 7 = 9)
Solution: Hash Table
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
if (map.find(nums[i]) != map.end()) {
vector<int> result = {map[nums[i]], i};
return result;
}
else {
map[target - nums[i]] = i;
}
}
}
A thorough writeup of this solution can be found here.