[導讀]一組漫畫告訴你！
—————? 第二天? —————
什么意思呢？我們來舉個例子，給定下面這樣一個整型數組（題目假定數組不存在重復元素）：
我們隨意選擇一個特定值，比如13，要求找出兩數之和等于13的全部組合。
由于12+1 = 13，6+7 = 13，所以最終的輸出結果（輸出的是下標）如下：
【1， 6】
【2， 7】
小灰想表達的思路，是直接遍歷整個數組，每遍歷到一個元素，就和其他元素相加，看看和是不是等于那個特定值。
第1輪，用元素5和其他元素相加：
沒有找到符合要求的兩個元素。
第2輪，用元素12和其他元素相加：
發(fā)現12和1相加的結果是13，符合要求。
按照這個思路，一直遍歷完整個數組。
————————————
讓我們來具體演示一下：
第1輪，訪問元素5，計算出13-5=8。在哈希表中查找8，發(fā)現查不到：
第2輪，訪問元素12，計算出13-12=1。在哈希表中查找1，查到了元素1的下標是6，所以元素12（下標是1）和元素1（下標是6）是一對結果：
第3輪，訪問元素6，計算出13-6=7。在哈希表中查找7，查到了元素7的下標是7，所以元素6（下標是2）和元素7（下標是7）是一對結果：
按照這個思路，一直遍歷完整個數組即可。
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)));
????????????????//為防止找到重復的元素對，匹配后從哈希表刪除對應元素
????????????????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é)快要到了，小灰給大家準備了一個福利，
掃碼關注下方公眾號，回復關鍵字“奶茶”，可以參與抽獎：
點個[在看]，是對小灰最大的支持！
免責聲明：本文內容由21ic獲得授權后發(fā)布，版權歸原作者所有，本平臺僅提供信息存儲服務。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯系我們，謝謝！
下載文檔
