Two Sum

• leetcode 1
• Easy
• Company Tag: LinkedIn, Uber, Airbnb, Facebook, Amazon, MicroSoft, Apple, Yahoo, Dropbox, Bloomberg, Yelp, Adobe
• Tags: Array, Hash Table
• Sow Similar Problem: 3Sum, 4Sum, Two Sum II, Two Sum III

Description

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.

Example: Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

C++ Solution

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> dict;
        vector<int> res;

        for(int i = 0; i < nums.size(); i++){
            if( dict.find(target - nums[i]) != dict.end()){
                res.push_back(dict[target - nums[i]]);
                res.push_back(i);
                break;
            }else{
                dict[nums[i]] = i;
            }
        }
        return res;
    }
};

Java Solution

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> dict = new HashMap();
        int[] res = new int[2];

        for(int i = 0; i < nums.length; i++){
            if(dict.containsKey(target - nums[i])){
                res[0] = dict.get(target - nums[i]);
                res[1] = i;
                break;
            }else{
                dict.put(nums[i], i);
            }
        }
        return res;
    }
}