【題目描述】
Given an array of integers, find two numbers such that they add up to a specific target number.The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.
Notice:You may assume that each input would have exactly one solution
給一個(gè)整數(shù)數(shù)組正塌，找到兩個(gè)數(shù)使得他們的和等于一個(gè)給定的數(shù) target。你需要實(shí)現(xiàn)的函數(shù)twoSum需要返回這兩個(gè)數(shù)的下標(biāo), 并且第一個(gè)下標(biāo)小于第二個(gè)下標(biāo)润绎。注意這里下標(biāo)的范圍是 1 到 n冠胯，不是以 0 開頭墓贿。
注意:你可以假設(shè)只有一組答案。
【題目鏈接】
www.lintcode.com/en/problem/two-sum/
【題目解析】
三種解法。
解法一窜锯， hash
從左往右掃描一遍艘刚，然后將數(shù)及坐標(biāo)管宵，存到map中。然后再掃描一遍即可攀甚。時(shí)間復(fù)雜度O(n)
解法二箩朴，雙指針掃描
將數(shù)組排序，然后雙指針從前后往中間掃描秋度。時(shí)間復(fù)雜度O(n*lgn)炸庞。因?yàn)槭且蠓祷卦瓟?shù)組的下標(biāo)，所以在排序的時(shí)候還得有額外的數(shù)組來存儲(chǔ)下標(biāo)信息静陈， 也挺麻煩燕雁。
解法三诞丽，暴力搜索
這個(gè)倒是最省事的。時(shí)間復(fù)雜度O(n*n)
【參考答案】
