漫畫(huà)：如何在數(shù)組中找到和為 “特定值” 的兩個(gè)數(shù)？
—————? 第二天? —————
什么意思呢？我們來(lái)舉個(gè)例子，給定下面這樣一個(gè)整型數(shù)組（題目假定數(shù)組不存在重復(fù)元素）：
我們隨意選擇一個(gè)特定值，比如13，要求找出兩數(shù)之和等于13的全部組合。
由于12+1 = 13，6+7 = 13，所以最終的輸出結(jié)果（輸出的是下標(biāo)）如下：
【1， 6】
【2， 7】
小灰想表達(dá)的思路，是直接遍歷整個(gè)數(shù)組，每遍歷到一個(gè)元素，就和其他元素相加，看看和是不是等于那個(gè)特定值。
第1輪，用元素5和其他元素相加：
沒(méi)有找到符合要求的兩個(gè)元素。
第2輪，用元素12和其他元素相加：
發(fā)現(xiàn)12和1相加的結(jié)果是13，符合要求。
按照這個(gè)思路，一直遍歷完整個(gè)數(shù)組。
————————————
讓我們來(lái)具體演示一下：
第1輪，訪問(wèn)元素5，計(jì)算出13-5=8。在哈希表中查找8，發(fā)現(xiàn)查不到：
第2輪，訪問(wèn)元素12，計(jì)算出13-12=1。在哈希表中查找1，查到了元素1的下標(biāo)是6，所以元素12（下標(biāo)是1）和元素1（下標(biāo)是6）是一對(duì)結(jié)果：
第3輪，訪問(wèn)元素6，計(jì)算出13-6=7。在哈希表中查找7，查到了元素7的下標(biāo)是7，所以元素6（下標(biāo)是2）和元素7（下標(biāo)是7）是一對(duì)結(jié)果：
按照這個(gè)思路，一直遍歷完整個(gè)數(shù)組即可。
public?class?FindSumNumbers?{
????public?static?List>?twoSum(int[]?nums,?int?target)?{
????????Map?map?=?new?HashMap<>();
????????List>?resultList?=?new?ArrayList<>();
????????for?(int?i?=?1;?i?????????????map.put(nums[i],?i);
????????}
????????for?(int?i?=?0;?i?????????????int?other?=?target?-?nums[i];
????????????if?(map.containsKey(other)?&&?map.get(other)?!=?i)?{
????????????????resultList.add(Arrays.asList(i,map.get(other)));
????????????????//為防止找到重復(fù)的元素對(duì)，匹配后從哈希表刪除對(duì)應(yīng)元素
????????????????map.remove(nums[i]);
????????????}
????????}
????????return?resultList;
????}
????public?static?void?main(String[]?args)?{
????????int[]?nums?=?{5,12,6,3,9,2,1,7};
????????List>?resultList?=?twoSum(nums,?13);
????????for(List?list?:?resultList){
????????????System.out.println(Arrays.toString(list.toArray()));
????????}
????}
}
????public?static?List>?twoSumV2(int[]?nums,?int?target)?{
????????Map?map?=?new?HashMap<>();
????????List>?resultList?=?new?ArrayList<>();
????????for?(int?i?=?0;?i?????????????int?other?=?target?-?nums[i];
????????????if?(map.containsKey(other))?{
????????????????resultList.add(Arrays.asList(map.get(other),i));
????????????}
????????????map.put(nums[i],?i);
????????}
????????return?resultList;
????} 中秋節(jié)快要到了，小灰給大家準(zhǔn)備了一個(gè)福利，
掃碼關(guān)注下方公眾號(hào)，回復(fù)關(guān)鍵字“奶茶”，可以參與抽獎(jiǎng)：
點(diǎn)個(gè)[在看]，是對(duì)小灰最大的支持！
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
