Lintcode: 2 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.

Have you met this question in a real interview? 

Yes

Example

numbers=[2, 7, 11, 15], target=9

return [1, 2]

Note

You may assume that each input would have exactly one solution

Challenge

Either of the following solutions are acceptable:

• O(1) Space, O(nlogn) Time
• O(n) Space, O(n) Time

Tags Expand 

Two Pointers Sort Array

Hashmap solution:
O(n) Space, O(n) Time solution:
Use a hashmap to store element of array as key, index as value.
Then use a for loop to check whether target - current exist in hashmap.
However, if element in the array is repeated, the hashmap has to hold repetitive keys.
So we keep comparing and storage at the same time and don't need to worry about repetitions.

class Solution {
public:
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1+1, index2+1] (index1 < index2)
     */
    vector<int> twoSum(vector<int> &nums, int target) {
        // write your code here
        vector<int> result;
        unordered_map<int, int> hashmap;
        for(int i = 0; i < nums.size(); i++){
            if(hashmap.find(target - nums[i]) != hashmap.end()) {
                result.push_back(hashmap[target - nums[i]] + 1);
                result.push_back(i + 1);
                return result;
            }
            else hashmap[nums[i]] = i;
        }
        //if two numbers don't exist.
        result.push_back(0);
        result.push_back(0);
        return result;
    }
};

Sorting solution:
O(1) Space, O(nlogn) Time:
nlogn is obvious to sort the array. Since we need to return the indexes, so we need to record index when sorting.
1) use pair
2) write a structure
    http://www.acmerblog.com/leetcode-two-sum-5223.html
3) use a for loop to look for the indexes of the required two numbers, stupid, but don't affect the time complexity any way.
Then use two pointers(head pointer, tail pointer) to look for target.

1)use pairt

class Solution {
public:
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1+1, index2+1] (index1 < index2)
     */
    vector<int> twoSum(vector<int> &nums, int target) {
        // write your code here
        vector< pair<int, int> > array; //vector<int> array(nums);
        for(int i = 0; i < nums.size(); i++){
            array.push_back(make_pair(nums[i], i + 1));
        }
        sort(array.begin(), array.end());
        vector<int> result;
        int i = 0;
        int j = nums.size() - 1;
        while(i < j){
            if(array[i].first + array[j].first > target) j--;
            else if(array[i].first + array[j].first < target) i++;
            else {
                result.push_back(min(array[i].second, array[j].second));
                result.push_back(max(array[i].second, array[j].second));
                return result;
            }
        }
        return result;
    }
};

2)use data structure

class Solution {
public:
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1+1, index2+1] (index1 < index2)
     */
     class Node{
         public:
         int val;
         int index;
         Node(int v, int i):val(v), index(i){}
     };//Don't forget semicolon
     //Note: comp function has to be static!!!!
     bool static comp(const Node& left, const Node& right){
         return left.val < right.val;
     }
     vector<int> twoSum(vector<int> &nums, int target) {
        // write your code here
        vector< Node > array; 
        for(int i = 0; i < nums.size(); i++){
            array.push_back(Node(nums[i], i + 1));
        }
        sort(array.begin(), array.end(), comp);
        vector<int> result;
        int i = 0;
        int j = nums.size() - 1;
        while(i < j){
            if(array[i].val + array[j].val > target) j--;
            else if(array[i].val + array[j].val < target) i++;
            else {
                result.push_back(min(array[i].index, array[j].index));
                result.push_back(max(array[i].index, array[j].index));
                return result;
            }
        }
        return result;
    }
};

3)use for loop

class Solution {
public:
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1+1, index2+1] (index1 < index2)
     */
    vector<int> twoSum(vector<int> &nums, int target) {
        // write your code here
        vector<int> array = nums; //vector<int> array(nums);
        sort(array.begin(), array.end());
        vector<int> result;
        int i = 0;
        int j = nums.size() - 1;
        int val1, val2;
        while(i < j){
            if(array[i] + array[j] > target) j--;
            else if(array[i] + array[j] < target) i++;
            else {
                val1 = array[i];
                val2 = target - array[i];
                break;
            }
        }
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == val1 || nums[i] == val2){
                result.push_back(i + 1);
            }
        }
        return result;
    }
};

K sum summary