Two Sum

Problem

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

You may assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Examples

Example 1:

Input: 
nums = [3,4,5,6], target = 7

Output: [0,1]

Explanation: nums[0] + nums[1] == 7, so we return [0, 1].

Example 2:

Input: nums = [4,5,6], target = 10

Output: [0,2]

Example 3:

Input: nums = [5,5], target = 10

Output: [0,1]

Constraints

• 2 <= nums.length <= 1000
• -10,000,000 <= nums[i] <= 10,000,000
• -10,000,000 <= target <= 10,000,000
• Only one valid answer exists.

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Solution

Walk through the list, and every number we see we store. The difference of target and the current item is the missing element, and we can check if we’ve seen this before.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> seen_values;
        for (std::size_t i = 0; i < nums.size(); ++i) {
            const auto &rhs = nums[i];
            const auto lhs = target - rhs;
            if (seen_values.contains(lhs)) {
                return std::vector<int>{seen_values[lhs], static_cast<int>(i)};
            }
            else {
                seen_values[rhs] = static_cast<int>(i);
            }
        }
    }
};