LeetCode:Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

---

The naive idea for this problem is using two for loops to check every possible pairs. This method cannot pass the large case.

Another idea is that use a hashmap to record the elements that have been visited, and meanwhile find if there exists one can be added to the current element to reach the target.

C++ Code:

/*
 * function: twoSum
 * goal: find the index of two integers whose sum is equal to the target
 * @param numbers: vector of the integers
 * @param target: the given target sum
 * return: the index of two integers, first one should be less than the second one
 */
/*
 * Basic Idea: Store integers into hashmap to help find
 * Complexity: time O(n), space O(n)
 */
vector<int> twoSum(const vector<int> &numbers, const int &target){
    //vector for the final result
    vector<int> result;
    
    //Corner Case 1: numbers is empty
    if(numbers.size() == 0){
        return result;
    }
    //Corner Case 2: there is only one element in numbers
    //According to the system, we have to return that one element if it is equal to
    //the target
    else if(numbers.size() == 1){
        if(numbers.at(0) == target){
            result.emplace_back(1);
        }
        return result;
    }
    else{
        //Use unordered_map to store value : index pair
        unordered_map<int, int> hash_map;
        for(size_t i = 0; i < numbers.size(); ++i){
            if(hash_map.find(target - numbers.at(i)) != hash_map.end()){
                result.emplace_back(hash_map[target - numbers.at(i)] + 1);
                result.emplace_back(i + 1);
                return result;
            }else{
                hash_map.emplace(numbers.at(i), i);
            }
        }
        //No matches
        return result;
    }
}

---

Python Code:

# func: find the index of two integers whose sum is equal to the target
# @param num: a list of input integers
# @param target: the given target sum
# @return: a tuple (index1, index2) where index1 < index2
# Basic Idea: Use dict to store the value and corresponding index
# Complexity: time O(n), space O(n)
def two_sum(num, target):
    #Corner Case 1: num is empty
    if not num:
        return
    #Corner case 2: there is only one element in num
    elif len(num) == 1:
        #If the element is equal to target, return it
        if num[0] == target:
            return (target)
        else:
            return
    #Common case: use dict to record previous element
    else:
        hash_map = {}
        for i in xrange(len(num)):
            #If we find that pair, return it
            if (target - num[i]) in hash_map:
                return (hash_map[target-num[i]]+1, i+1)
            else:
                hash_map[num[i]] = i

        #No matches
        return