LeetCode題解 || Two Sum問題

LeetCode題解 || Two Sum問題

question：

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

思路：

輸入一個無序數組和一個目標和，求出兩個數之和為這個目標數的下標，有大小之分。

目前想到三種方法：

（1）暴力枚舉法

遍歷整個數組，測試target與該數的差是否也在數組中，如果在，則這兩個數就是要找的，求出其下標即可。

時間復雜度為O（N*N），提交時提醒超時，被鄙視了。

（2）借助hashtable

C++ STL中沒有可以直接使用的hashtable模板類，可以使用其他庫實現的hashtable或者自己寫一個。

hashtable可以在O(1)時間復雜度下查找到一個元素，因此利用hashtable實現暴力枚舉法，時間復雜度會降低為O（N)

(3)雙指針

首先對數組排序，初始時一個指針指向數組第一個元素，另外一個指針指向最後一個元素，如果兩數之和大於target，右指針左移，相反，左指針右移。

排序時間復雜度為O(N*lg N)，查找時間復雜度為O（N），所以整體時間復雜度為O(N*lg N)

解題：

利用方法3中的思路

class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        vector tmp(numbers.size());//新建一個等大的數組
        vector res;//用於保存結果
        copy(numbers.begin(),numbers.end(),tmp.begin());//復制
        sort(tmp.begin(),tmp.end());//排序
        vector::iterator start=tmp.begin();//左指針
        vector::iterator terminate=tmp.end()-1;//右指針
        while((*start+*terminate)!=target)
        {
           if((*start+*terminate)>target)
              terminate--;
           if((*start+*terminate)::iterator a;
        vector::iterator b;
        if(*start!=*terminate)
        {
             a=find(numbers.begin(),numbers.end(),*start);
             b=find(numbers.begin(),numbers.end(),*terminate);
        }
        else
        {
            a=find(numbers.begin(),numbers.end(),*start);
            b=find(a+1,numbers.end(),*terminate);//第二次查找起點不一樣
        }
       res.push_back(a-numbers.begin()+1);
       res.push_back(b-numbers.begin()+1);
       sort(res.begin(),res.end());
        return res;
    }
};

Submission Result: Accepted