1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]. 

JAVA

public class Solution {

    public int[] twoSum(int[] nums, int target) {

        // set up hashmap: remaining to original. thread-unsafe but for here is ok
        HashMap<Integer, Integer> hm = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {

            // if key in hm, result found.
            // so that only one pass
            if (hm.containsKey(nums[i])) {
                int otherIndex = hm.get(nums[i]);

                return new int[]{Math.min(i, otherIndex) + 1, Math.max(i, otherIndex) + 1};
            }
            // put new record into hashmap
            else {
                hm.put(target - nums[i], i);
            }
        }

        return null;
    }

}

PYTHON

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

JAVASCRIPT

var twoSum = function (nums, target) {
    const m = new Map();
    for (let i = 0; ; ++i) {
        const x = nums[i];
        const y = target - x;
        if (m.has(y)) {
            return [m.get(y), i];
        }
        m.set(x, i);
    }
};

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& A, int target) {
        vector<vector<int>> v;
        int N = A.size(), L = 0, R = N - 1;
        for (int i = 0; i < N; ++i) v.push_back({ A[i], i });
        sort(begin(v), end(v));
        while (L < R) {
            int sum = v[L][0] + v[R][0];
            if (sum == target) return { v[L][1], v[R][1] };
            if (sum < target) ++L;
            else --R;
        }
        return {};
    }
};