LeetCode第一題：兩數之和（two sum）C++實作

說來慚愧。當時大學開始的時候，我偶爾還會刷刷acm，後來确定保研了，代碼都不咋寫了，目前碼代碼很生疏了，現在滿心的後悔（當然世界上沒有後悔藥可以買/(ㄒoㄒ)/~~），我可不是替我的菜找借口啊 。

下面進入正題，開始我最直接的解題思路是這樣的：首先對數組的元素進行排序，并且得到排序後各個元素的原來索引，（也就是元素大小在進行排序的過程中位置發生改變，索引是原來的索引值，但是位置也相應變化），那麼這樣就隻要在數組中搜尋小于target的前n個元素，對這些進行暴力周遊即可。後來想了一想，還不如直接暴力法呢，排序幹嘛，我總是想的好複雜啊（就是自己太弱雞了）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> index;
        vector<int> res;
        int length = nums.size();
        int num_size = nums.size();


        for(int i=0; i<num_size; i++) {
            index.push_back(i+1);
        }

        for(int j=0; j<num_size; j++) {
            for(int k=0; k<num_size-j-1; k++) {
                if(nums[k] > nums[k+1]) {
                    int temp = nums[k];
                    nums[k] = nums[k+1];
                    nums[k+1] = temp;

                    int temp_index = index[k];
                    index[k] = index[k+1];
                    index[k+1] = temp_index;
                }
            }
        }

        for(int m=0; m<num_size; m++) {
            if(target >= *max_element(nums.begin(), nums.end())) {
                length = num_size;
            }
            else if(target < nums[m]) {
                length = m+1;
                break;
            }
        }

        for(int n=0; n<length; n++) {
            for(int p=n+1; p<length; p++) {
                if(nums[n]+nums[p] == target) {
                    res.push_back(index[n]);
                    res.push_back(index[p]);
                    sort(res.begin(), res.end());

                    return res;
                }
            }
        }
    }

};
           

接下來是官方的解題方法：

//方法二 C++版本的兩遍哈希表（官方題解）
/*
通過以空間換取速度的方式，我們可以将查找時間從 O(n) 降低到 O(1)。
C++版本的哈希表算法采用unordered_map。
*/
vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> ans;
    unordered_map<int,int> tmpmap;
    int length = nums.size();
    for(int i = 0;i < length;i++){
        tmpmap[nums[i]] = i;
    }
    for (int i = 0; i < length; i++){
        if(tmpmap.count(target - nums[i]) != 0 && tmpmap[target - nums[i]] != i){  
        //使用count，傳回的是被查找元素的個數。如果有，傳回1；否則，傳回0。
            ans.push_back(i);
            ans.push_back(tmpmap[target - nums[i]]);
            break;
        }
    }
    return ans;
}

//方法三 C++版本的一遍哈希表（官方題解）
/*
事實證明，我們可以一次完成。在進行疊代并将元素插入到表中的同時，我們還會回過頭來檢查
表中是否已經存在目前元素所對應的目标元素。如果它存在，那我們已經找到了對應解，并立即将其傳回。
*/
vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> ans;
    unordered_map<int,int> tmpmap;
    int length = nums.size();
    for (int i = 0; i < length; i++){
        if(tmpmap.count(nums[i]) != 0){
            ans.push_back(tmpmap[nums[i]]);
            ans.push_back(i);
            break;
        }
        tmpmap[target - nums[i]] = i;
    }
    return ans;
}