原題鏈接
題目原文：
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ù)數(shù)組，返回（兩個數(shù)字加起來的和等于給定的目標數(shù)字）的位置（即數(shù)組下標）
你可以假定每個輸入例子正好只有一個解，并且你不能夠使用同一個元素兩次。
這是leetcode的第一題，屬于給新手練習用的基礎(chǔ)題。無論從什么角度來說，這個題目只要是會寫代碼的同學，沒有誰是想不到解法的。
但是新手往往會陷入一個問題，但凡解題都會選擇使用暴力破解辦法（brute force）,這樣空間復(fù)雜度往往會特別大，也是實際應(yīng)用和面試的大忌，當然，只有在萬不得已的情況下才可以考慮暴力破解。
暴力破解法: 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}
}
