1. Two Sum

LC1

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to 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 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2)time complexity?

Solution:

JavaScript

var twoSum = function(nums, target) {
    const mp = new Map();
    nums.forEach((num, index) => {
        mp.set(num, index);
    })
    const result = [];
    nums.forEach((num, index) => {
        const remaining = target-num;
        if (mp.has(remaining) && mp.get(remaining) != index && result.length == 0) {
            result.push(index);
            result.push(mp.get(remaining));
        }
    })
    return result;
};

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        map<int,int> mp;
        for (int i = 0; i < nums.size(); i++) {
            if (!mp[nums[i]]) {
                mp[nums[i]] = i;
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            if (mp[target-nums[i]] && mp[target-nums[i]]!=i) {
                result.push_back(i);
                result.push_back(mp[target-nums[i]]);
                break;
            }
        }
        return result;
    }
};

Approach: Two-pass Hash Table

Intuition

To improve our runtime complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to get its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

Algorithm

A simple implementation uses two iterations. In the first iteration, we add each element's value as a key and its index as a value to the hash table. Then, in the second iteration, we check if each element's complement (target-nums[i]) exists in the hash table. If it does exist, we return current element's index and its complement's index. Beware that the complement must not be nums[i] itself!