1. Two Sum

Problem #1 (Two Sum | Array, Hash Table)

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]

---

Constraint

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

---

SOLUTIONS

HashMap

We create a HashMap that contains <Integer, Integer>, the key is the element from the array and value is its index,

We create a for loop to iterate through each element of the array. Each element is mapped to the HashMap,

An operation is perforned target - element that is stored to variable pair, which represents the number needed to be added to the current element to get the target. The HashMap is checked if it already contains the number pair. If it is, then return the index of the current element and the index of pair.

• JAVA

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < nums.length; i++){
            int pair = target - nums[i];
            if(map.containsKey(pair))
                return new int[]{map.get(pair), i};
            map.put(nums[i], i);
        }
        return new int[]{};
    }
}

• C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> map;
        for(int i = 0; i < nums.size(); i++){
            int pair = target - nums[i];
            if(map.count(pair)) return {map[pair], i};
            map[nums[i]] = i;
        }
        return {};
    }
};

Complexity

• Time: O(n)
• Space: O(n)

• Ruby

def two_sum(nums, target)
    hash = {}
    nums.each_with_index do |num, idx|
        complement = target - num
        return [hash[complement], idx] if hash.key?(complement)
        hash[num] = idx
    end
end

• Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i, num in enumerate(nums):
            if target - num in d:
                return [d[target - num], i]
            d[num] = i
        return []

• PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
    $map = [];
    for ($i = 0; $i < count($nums); $i++) {
        $complement = $target - $nums[$i];
        if (isset($map[$complement])) {
            return [$map[$complement], $i];
        }
        $map[$nums[$i]] = $i;
    }
}

}

• JavaScript

const twoSum = function (nums, target)
{
    //search of all Array
    for (let i = 0; i < nums.length; i++)
    {
        for (let j = i + 1; j < nums.length; j++)
        {
            // if (nums[j] === target - nums[i])
            if(nums[i] + nums[j] === target)
            {
                return [i, j];
            }
        }
    }
    };

• C#

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
    Dictionary<int, int> map = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++) {
        int complement = target - nums[i];
        if (map.ContainsKey(complement)) {
            return new int[] { map[complement], i };
        }
        map[nums[i]] = i;
    }
    throw new Exception("No two sum solution");
}

}