原題鏈接
題目原文：
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].
中文翻譯：
給定一個(gè)整數(shù)數(shù)組误续，返回（兩個(gè)數(shù)字加起來(lái)的和等于給定的目標(biāo)數(shù)字）的位置（即數(shù)組下標(biāo)）
你可以假定每個(gè)輸入例子正好只有一個(gè)解，并且你不能夠使用同一個(gè)元素兩次。
這是leetcode的第一題庆揪，屬于給新手練習(xí)用的基礎(chǔ)題定鸟。無(wú)論從什么角度來(lái)說(shuō)，這個(gè)題目只要是會(huì)寫(xiě)代碼的同學(xué)报强，沒(méi)有誰(shuí)是想不到解法的懒鉴。
但是新手往往會(huì)陷入一個(gè)問(wèn)題，但凡解題都會(huì)選擇使用暴力破解辦法（brute force）,這樣空間復(fù)雜度往往會(huì)特別大瞻离，也是實(shí)際應(yīng)用和面試的大忌雁仲，當(dāng)然，只有在萬(wàn)不得已的情況下才可以考慮暴力破解琐脏。
暴力破解法: O(n ^ 2) time
vector<int> twoSum(vector<int>& nums, int target) {
? ? for (int i = 0; i < nums.size(); i++) {
? ? ? ? for (int k = 0; k < nums.size(); k++) {
? ? ? ? ? ? if (i != k) {
? ? ? ? ? ? ? ? if (nums[i] + nums[k] == target)
? ? ? ? ? ? ? ? ? ? return {i, k};
????????????}
????????}
????}
? ? return {-1, -1};
}
優(yōu)化版暴力破解：O(n*logn) time
vector<int> twoSum(vector<int>& nums, int target) {? ?
????for (int i = 0; i < nums.size(); i++) {? ? ? ?
????????for (int k = i + 1; k < nums.size(); k++) { ? ? ? ? ??
????????????????if (nums[i] + nums[k] == target)? ? ? ? ? ? ? ? ? ?
????????????????????return {i, k};????????????
????????????????} ?
????}
? ? return {-1, -1};
}
一次遍歷解法：O(n) time O(n)space
vector<int> twoSum(vector<int>& nums, int target) { ?
? ? unordered_map<int, int> rec;
? ? for (int i = 0; i < nums.size(); i++) {
? ? ? ? if (rec.find(target - nums[i]) != rec.end())
? ? ? ? ? ? return {rec[target - nums[i]], i};
? ? ? ? rec[nums[i]] = i;
????}
? ? return {-1, -1}
}
