題目鏈接
tag:

• Easy；

question:
??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].

思路：
??本道題給一個數(shù)組，一個目標(biāo)數(shù)target，讓我們找到兩個數(shù)字，使其和為target，第一感覺暴力搜索，但是猜到OJ肯定不會允許用這么簡單的方法，于是去試了一下，果然是Time Limit Exceeded，這個算法的時間復(fù)雜度是O(n^2)。那么只能想個O(n)的算法來實現(xiàn)，由于暴力搜索是遍歷所有的兩個數(shù)字的組合，這樣雖然節(jié)省了空間，但時間復(fù)雜度高。一般來說，我們?yōu)榱颂岣邥r間的復(fù)雜度，需要用空間來換，這算是一個trade-off吧，用線性的時間復(fù)雜度來解決問題，那么就是說只能遍歷一個數(shù)字，那么另一個數(shù)字呢，我們可以事先將其存儲起來，使用一個HashMap，來建立數(shù)字和其坐標(biāo)位置之間的映射，HashMap是常數(shù)級的查找效率，這樣，我們在遍歷數(shù)組的時候，用target減去遍歷到的數(shù)字，就是另一個需要的數(shù)字了，直接在HashMap中查找其是否存在即可，注意要判斷查找到的數(shù)字不是第一個數(shù)字，比如target是4，遍歷到了一個2，那么另外一個2不能是之前那個2，整個實現(xiàn)步驟為：先遍歷一遍數(shù)組，建立HashMap映射，然后再遍歷一遍，開始查找，找到則記錄index。代碼如下：

C++ 解法：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 兩次遍歷+哈希
        vector<int> res;
        unordered_map<int, int> m;
        if (nums.size() < 2)
            return res;
        for (int i=0; i<nums.size(); ++i)
            m[nums[i]] = i;
        for (int i=0; i<nums.size(); ++i) {
            int tmp = target - nums[i];
            if (m.count(tmp) && m[tmp] != i) {
                res.push_back(i);
                res.push_back(m[tmp]);
                break;
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 一次遍歷+哈希
        vector<int> res;
        if (nums.size() < 2) {
            return res;
        }
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            int tmp = target - nums[i];
            if (m.count(tmp) && m[tmp] != i) {
                res.push_back(i);
                res.push_back(m[tmp]);
                break;
            }
            m[nums[i]] = i;
        }
        return res;
    }
};

Python 解法：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        res = []
        if len(nums) < 2:
            return res
        m = {}
        for i in range(len(nums)):
            m[nums[i]] = i
        for i in range(len(nums)):
            diff = target - nums[i]
            if diff in m.keys() and (i != m[diff]):
                res.append(i)
                res.append(m[diff])
                break
        return res