【題目描述】
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)
【參考答案】
