Finding Two Numbers That Sum to a Target Value
Given an integer array values and a target integer goal, find the two numbers within the array whose sum equals goal and return their indices.
Example 1:
Input: values = [2,7,11,15], goal = 9
Output: [0,1]
Explanation: values[0] + values[1] == 9.
Example 2:
Input: values = [3,2,4], goal = 6
Output: [1,2]
Example 3:
Input: values = [3,3], goal = 6
Output: [0,1]
Approach 1: Brute Force
Time Complexity: O(n²)
Iterate through all possilbe pairs of indices i and j (where j < i) and check if their sum equals the target.
class Solution {
public:
vector<int> twoSum(vector<int>& values, int goal) {
vector<int> result;
for (int i = 0; i < values.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (values[i] + values[j] == goal) {
result = {j, i};
return result;
}
}
}
return result;
}
};
Approach 2: Hash Map
Time Complexity: O(n)
Utilize a hash map to store each element's value and its index. For each element values[i], check if the complement goal - values[i] already exists in the map.
class Solution {
public:
vector<int> twoSum(vector<int>& values, int goal) {
unordered_map<int, int> valueIndexMap;
for (int i = 0; i < values.size(); ++i) {
int complement = goal - values[i];
if (valueIndexMap.find(complement) != valueIndexMap.end()) {
return {valueIndexMap[complement], i};
}
valueIndexMap[values[i]] = i;
}
return {};
}
};
