Two Sum 問題

這題雖然簡單，但是有一些資料結構的細節值得記錄，下面列的兩種解法代表 Hash table 和 Array 兩種不同的資料結構思維。

一、Two Sum 問題

Leetcode OJ - Two Sum Problem : https://leetcode.com/problems/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

二、Two Sum 問題詳解

1. Hash Table 解：使用 C++ 的 map

使用 Hash 解，關鍵就在 Find() 這個操作子的複雜度，總複雜度為O( N * FindComplex )。本題我使用 map 容器作為 Hash Table，因此複雜度為O(NlogN)。

class Solution {
public:
    // Two Sum Solution
    //      @ Total Complexity : O(NlogN), where N is nums size
    //      @ FIND() operator in map :  O(logN), key look up in red black tree
   
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> hashTable;
        map<int,int>::iterator iter;
        vector<int> ansIndex(2);
       
        for(int i = 0; i < nums.size(); i++){
            int x = nums[i];
            iter = hashTable.find(target - x);
           
            if(iter != hashTable.end()){
                ansIndex[0] = iter->second + 1;
                ansIndex[1] = i + 1;
                return ansIndex;
            }
            else
                hashTable[x] = i;
        }
       
        cout<<"no answer.."<<endl;
    }
};

2. 陣列解：使用 C++ 的 vector

使用Array解，關鍵在 Sort() 這個操作子的複雜度，總複雜度即與Sort()複雜度相同。本題我使用 C++的 sort 因此複雜度為O(NlogN)。

class Solution {
public:
    // Two Sum Solution
    //      @ Total Complexity : O(NlogN)
    //      @ SORT() : O(NlogN)
 
   struct sort_pred {
        bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right{
            return left.first < right.first;
        }
    };
 
    const int reserveNum = 1024;

    vector<int> twoSum(vector<int>& nums, int target) {
        vector< pair<int, int> > numList;
        vector<int> ansIndex(2);
        numList.reserve(reserveNum);
     
        for(int i = 0; i < nums.size(); i++)
            numList.push_back(make_pair(nums[i] ,i));
     
        sort(numList.begin(), numList.end(), sort_pred());
         
        int i = 0, j = nums.size()-1;
     
        while(i < j){
            int sum = numList[i].first + numList[j].first;
            if(sum < target)
                i++;
            else if (sum > target)
                j--;
            else{
                if(numList[i].second < numList[j].second){
                    ansIndex[0] = numList[i].second+1;
                    ansIndex[1] = numList[j].second+1;
                }
                else{
                    ansIndex[0] = numList[j].second+1;
                    ansIndex[1] = numList[i].second+1;
                }
                return ansIndex;
            }
        }
     
        cout<<"no answer.."<<endl;
    }
};

三、 Hash Table 解與陣列解的效率探討

雖然最後得出的複雜度相同，甚至 hash table 的解法中的 Find() 可抽換成O(1)的 hash 函式而達到O(n) 的時間複雜度，但實際跑起來的速度基本上還是陣列解較快，因為陣列較貼近記憶體實際的排列。

1. Hash Table 解

2. 陣列解

References

Leetcode OJ - Two Sum Problem
https://leetcode.com/problems/two-sum/

【心得】C++ STL-Introduction to pair<T1, T2>
http://forum.gamer.com.tw/Co.php?bsn=60292&sn=3518

Stackoverflow - use a custom comparator
http://stackoverflow.com/questions/279854/how-do-i-sort-a-vector-of-pairs-based-on-the-second-element-of-the-pair