Problem declaration

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].

Solution 1: force searching

Consider intern and extern loop to find two number summed as target, which comes up with the algothrim with complexity O(n*n).

Solution 2: hash

Consider using hash table. If the searching pointer points a number, two scenarios should be there:

1. The value [target - number ] is not in the hash table, then we add the number into the table.
2. The value [target - number] is in the hash table, then we get answer for the problem.

solution.h

#ifndef CLIONPROJECTS_SOLUTION_H
#define CLIONPROJECTS_SOLUTION_H

#include <vector>
#include <hash_map>

class Solution {
    public:
        //Constructor
        Solution();
        ~Solution();

        typedef std::vector<int> IntVector;

        IntVector TwoSum(IntVector&, int);

    private:
        typedef __gnu_cxx::hash_map<int,int> IHashMap;
        IHashMap map;
        IntVector result;
};

#endif //CLIONPROJECTS_SOLUTION_H

solution.cpp

#include "solution.h"

Solution::Solution() = default;

Solution::~Solution() = default;

Solution::IntVector Solution::TwoSum(Solution::IntVector& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        if (map.find(target - nums[i]) != map.end()) {
            result.push_back(i);
            result.push_back(map.find(target - nums[i]) -> second);
            break;
        } else {
            map[nums[i]] = i;
        }
    }
    return result;
}

main.cpp

#include <iostream>
#include "solution.h"

using std::cout;
using std::endl;

int main(int argc, char* argv[]) {
    int nums_array[] = {2, 7, 11, 15};
    int target = 9;
    Solution::IntVector nums(nums_array, nums_array + 4);
    auto * test = new Solution();
    auto result = test -> TwoSum(nums, target);

    //sort the indexes
    std::sort(result.begin(), result.end());

    cout << "[";
    for (auto it = result.begin(); it != result.end() - 1; it++) {
        cout << *it << ", ";
    }
    cout << *(result.end() - 1) << "]" << endl;
    return 0;
}

The solution mentioned above is faster than previous one, which complexity is O(n). However, it needs extra memory space to store hash table.

Solution 3: double pointer

Consider that there are two pointer existing. For a sorted array(ascending for example), there are two numbers which point lo&hi pointing at respectively, if the sum of these two numbers larger than target, we increase lo by lo++, else make hi--. The algorithm complexity of sorting the array should be O(nlogn), and the complexity of finding sum of target is O(n). Though it is larger than the solution2, it's an in-place algorithm.

solution.cpp

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> nums_cpy;
        nums_cpy.assign(nums.begin(), nums.end());
        std::sort(nums_cpy.begin(), nums_cpy.end());
        
        auto lo = nums_cpy.begin();
        auto hi = nums_cpy.end() - 1;
        vector<int> result;
        while (lo <= hi) {
            if (*lo + *hi == target) {
                for (int i = 0; i < nums.size(); i++) {
                    if (nums[i] == *lo) {
                        result.push_back(i);
                    } else if(nums[i] == *hi) {
                        result.push_back(i);
                    }
                }
                return result;
            } else if (*lo + *hi < target) {
                lo++;
            } else {
                hi--;
            }
        }
    }
};