題目

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

解題思路

題目的意思很簡(jiǎn)單，給你一個(gè)數(shù)組 nums[] 和一個(gè)target值，然后在該數(shù)組里找出兩個(gè)元素，使得他們加起來(lái)的和等于target值，最后返回他們的indices。

1. 最粗糙的方法肯定就是暴力求解啦，不過(guò)時(shí)間復(fù)雜度為 O(n^2), 為下下策。
2. 接著再想到一個(gè)方法，那就是第一步先對(duì)數(shù)組排序，時(shí)間復(fù)雜度為 O(nlog(n))。 然后第二步設(shè)兩個(gè)索引 a = 0, b = n-1, 如果 nums[a] + nums[b] > target, 則 b--；如果 nums[a] + nums[b] < target, 則 a++；如果 nums[a] + nums[b] = target, 則返回 a, b 值。第二步的時(shí)間復(fù)雜度為 O(n), 所以該算法總的時(shí)間復(fù)雜度為 O(nlog(n))，該算法的代碼我沒(méi)有貼出來(lái)，因?yàn)楹苋菀拙湍軐?xiě)出來(lái)。
3. 第三個(gè)方法是看到討論區(qū)有人給出自己的解法，我看到挺有意思的。他是利用了哈希表的方法。原理也很簡(jiǎn)單，首先建立一個(gè)哈希表，然后遍歷一遍數(shù)組，每次遍歷的時(shí)候，檢查在哈希表里是否存在一個(gè)元素，使得它們兩個(gè)相加等于 target 值，如果有則輸出答案，如果沒(méi)有則將該遍歷到的元素插進(jìn)哈希表中，并記錄下它的 index 值。遍歷的時(shí)間復(fù)雜度為 O(n), 每次遍歷的時(shí)候在哈希表里檢索的時(shí)間為 O(log(n)), 所以總的復(fù)雜度也為 O(nlog(n))，但是那個(gè)人說(shuō)是 O(n), 他認(rèn)為哈希表里檢索是不需要時(shí)間的，但我認(rèn)為 unordered_map 里面使用紅黑樹(shù)實(shí)現(xiàn)的，檢索是有代價(jià)的，所以我覺(jué)得復(fù)雜度為 O(nlog(n))。實(shí)現(xiàn)代碼如下：

參考代碼

一、排序方法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        unordered_map<int, int> hash, temp;
        //map<int, int> hash;
        for(int i=0;i<nums.size() ;i++){
            if(hash.find(nums[i])==hash.end())
                hash[nums[i]]=i;
            else
                temp[nums[i]]=i;
        }
        
        sort(nums.begin() ,nums.end());
        int i=0, j=nums.size()-1;
        while(i<j){
            if(nums[i]+nums[j]==target){
                if(nums[i]==nums[j]){
                    ans.push_back(hash[nums[i]]);
                    ans.push_back(temp[nums[i]]);
                }
                else{  
                    ans.push_back(hash[nums[i]]);
                    ans.push_back(hash[nums[j]]); 
                }
                break;
            }
            else if(nums[i]+nums[j]<target)
                i++;
            else
                j--;
        }
        return ans;
    }
};

二、哈希方法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //Key is the number and value is its index in the vector.
        unordered_map<int, int> hash;
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) {
            int numberToFind = target - nums[i];

            //if numberToFind is found in map, return them
            if (hash.find(numberToFind) != hash.end()) {
                //+1 because indices are NOT zero based
                result.push_back(hash[numberToFind] );
                result.push_back(i );           
                return result;
            }

            //number was not found. Put it in the map.
            hash[nums[i]] = i;
        }
        return result;
    }
};

反思與總結(jié)

有人會(huì)認(rèn)為這題那么簡(jiǎn)單，為什么還要記錄下來(lái)。我認(rèn)為這題雖簡(jiǎn)單，但對(duì)我還是有一定啟發(fā)的。因?yàn)閷?duì) unordered_map, map 等這些數(shù)據(jù)結(jié)構(gòu)，雖然我了解他們的原理和實(shí)現(xiàn)，但往往在實(shí)際中很少會(huì)想起使用他們，從而導(dǎo)致自己的算法臃腫低效，所以我們應(yīng)該在實(shí)戰(zhàn)中多多利用這些封裝性強(qiáng)，效率高效并且使用簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，往往他們會(huì)出奇效~