【leetcode c++】twoSum

4月份接觸leetcode，沒多久就要準備考試大坑，已然忘記這玩意。最近得閑，便把已經寫好的leetcode整理一下發到部落格來。

（應該不會出問題吧第一次寫部落格→  →）

先上題目原文

Given anarray of integers, find two numbers such that they add up to a specific targetnumber.

Thefunction twoSum should return indices of the two numbers such that they add upto the target, where index1 must be less than index2. Please note that yourreturned answers (both index1 and index2) are not zero-based.

You mayassume that each input would have exactly one solution.

Input: numbers={2,7, 11, 15}, target=9

Output: index1=1, index2=2

題目大意：

提供一個整型數組，在數組中尋找兩個數使得這兩個數的和等于目标數值。

函數twoSum應該傳回這兩個數的下标，第一個下标應小于第二個下标，請注意下标不是基于零的（0是第一個下标）。

你可以假設所有的輸入都是有唯一解的。

解法1：最無腦的就是嵌套循環了。此略。

解法2：會不會覺得嵌套循環的時間複雜度稍微高了點呢？我們再重新審視題目，簡單地說題目的目的就是找到兩個數的下标……兩個數對應的下标……對應……key-value……對了就是關聯容器。

       由于本人使用c++語言，那麼就選用(multi)map了，為什麼要加了個(multi)呢？我們繼續探讨，是否有可能數組的的元素有重複。我們假設一種情況，Numebr={1, 1, 3, 4} target=2。這種情況下是否存在唯一解？答案是：是的。index1=1，index2=2。那麼數組元素是有重複元素的可能性了，是以最終決定要使用multimap。

       既然使用了關聯容器，那麼肯定不能再嵌套循環了，要在一次for循環内結束戰鬥。在嵌套循環的做法中我們是這麼做的：if(target == a + b )。能不能把b去掉，用别的已知變量代替呢？比如這樣：if(target == a + (target- a) )。好吧，這樣子看起來确實很愚蠢，去括号之後就變成target == target了，但是這是個很好的思路。我們換成另一個形式：

我們的multimap是以數組元素的值為鍵（key），以下标為值（value）的。那麼看這句。

numsMap.end() !=numsMap.find(target - iterator->first)  //target – a 存在

是不是明朗起來了？

但是不要着急，再給一種情況。Numebr={1, 3, 4} target=2。會發生什麼呢。會發生取了2次1的情況，是以存在解index1=1，index2=1。是以我們還要判斷，這組解的兩個數的下标不能相同。

if ((numsMap.end() != numsMap.find(target -iter1->first))   //存在a + b = target

       &&((numsMap.find(target - iter1->first))->second)!= iter1->second)   // 且a和b不是同一個下标

好了嗎？可以交卷了嗎？

請注意，傳回的兩個下标是升序的（where index1 must be less than index2），是以最後還要排序一下。

懶人版就是：sort(res.begin(), res.end());

Leetcode的AcceptedSolutions Runtime Distribution（這個截圖是5月上旬截的。灰色大柱子才是真正的you are here。黃色是c++紫色是c）

源碼：（VS2013）如果需要送出leetcode隻需要把twoSun函數中的代碼複制過去即可。

#include <vector>
#include <iostream>
#include <map>
#include <algorithm>  

using namespace std;

vector<int> twoSum(vector<int>&, int);

int main()
{
	vector<int> nums = {0,2,4,0 };
	cout << twoSum(nums, 0)[0] << " " << twoSum(nums, 0)[1];
	return 0;
}

vector<int> twoSum(vector<int>& nums, int target){
	vector<int> res;
	multimap<int, int> numsMap;
	multimap<int, int>::iterator iter1;
	int max = nums.size();

	//數組轉進map，用下标做鍵
	for (int i = 0; i < max; i++)
	{
		numsMap.insert(pair<int, int>(nums[i], i + 1));
	}

	for (iter1 = numsMap.begin(); iter1 != numsMap.end(); iter1++){

		//map.(target-a)存在，則存在a + b = target
		//且不是本身。
		if ((numsMap.end() != numsMap.find(target - iter1->first)) &&
			((numsMap.find(target - iter1->first))->second)//第二個下标，即(target-a)
			!= iter1->second)//第一個下标，即a
		{
			//将下标存到vector，并排序
			res.push_back((iter1->second));
			res.push_back((((numsMap.find(target - iter1->first))->second)));
			sort(res.begin(), res.end());
			break;
		}
	}

	return res;
}