漫畫算法題：兩數(shù)之和與三數(shù)之和
前一段時(shí)間，小灰分別講解了兩道leecode上的經(jīng)典算法題：
漫畫：如何在數(shù)組中找到和為 “特定值” 的兩個(gè)數(shù)？
漫畫：如何在數(shù)組中找到和為 “特定值” 的三個(gè)數(shù)？
今天，小灰把這兩道題整合起來(lái)，并修改了其中的細(xì)節(jié)問(wèn)題，感謝大家的指正。
————— 第二天 —————
什么意思呢？我們來(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 < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; 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 < nums.length; 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;
}
舉個(gè)例子，給定下面這樣一個(gè)整型數(shù)組（假定數(shù)組不存在重復(fù)元素）：
我們隨意選擇一個(gè)特定值，比如13，要求找出三數(shù)之和等于13的全部組合。
由于5+6+2=13， 5+1+7=13，3+9+1=13，所以最終的輸出結(jié)果如下（直接輸出元素值即可）：
【5， 6，2】
【5， 1，7】
【3， 9，1】
小灰的思路，是把原本的“三數(shù)之和問(wèn)題”，轉(zhuǎn)化成求n次“兩數(shù)之和問(wèn)題”。
我們以上面這個(gè)數(shù)組為例，選擇特定值13，演示一下小灰的具體思路：
第1輪，訪問(wèn)數(shù)組的第1個(gè)元素5，把問(wèn)題轉(zhuǎn)化成從后面元素中找出和為8（13-5）的兩個(gè)數(shù)：
如何找出和為8的兩個(gè)數(shù)呢？按照上一次所講的，我們可以使用哈希表高效求解：
第2輪，訪問(wèn)數(shù)組的第2個(gè)元素12，把問(wèn)題轉(zhuǎn)化成從后面元素中找出和為1（13-12）的兩個(gè)數(shù)：
第3輪，訪問(wèn)數(shù)組的第3個(gè)元素6，把問(wèn)題轉(zhuǎn)化成從后面元素中找出和為7（13-6）的兩個(gè)數(shù)：
以此類推，一直遍歷完整個(gè)數(shù)組，相當(dāng)于求解了n次兩數(shù)之和問(wèn)題。
public static List> threeSum(int[] nums, int target) {
List> resultList = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
Map map = new HashMap<>();
int d1 = target - nums[i];
//尋找兩數(shù)之和等于d1的組合
for (int j = i+1; j < nums.length; j++) {
int d2 = d1 - nums[j];
if (map.containsKey(d2)) {
resultList.add(Arrays.asList(nums[i], d2, nums[j]));
}
map.put(nums[j], j);
}
}
return resultList;
}
在上面的代碼中，每一輪解決“兩數(shù)之和問(wèn)題”的時(shí)間復(fù)雜度是O（n），一共迭代n輪，所以該解法總的時(shí)間復(fù)雜度是O（n2）。
至于空間復(fù)雜度，同一個(gè)哈希表被反復(fù)構(gòu)建，哈希表中最多有n-1個(gè)鍵值對(duì)，所以該解法的空間復(fù)雜度是O（n）。
我們?nèi)匀灰灾暗臄?shù)組為例，對(duì)數(shù)組進(jìn)行升序排列：
這樣說(shuō)起來(lái)有些抽象，我們來(lái)具體演示一下：
第1輪，訪問(wèn)數(shù)組的第1個(gè)元素1，把問(wèn)題轉(zhuǎn)化成從后面元素中找出和為12（13-1）的兩個(gè)數(shù)。
如何找出和為12的兩個(gè)數(shù)呢？我們?cè)O(shè)置兩個(gè)指針，指針j指向剩余元素中最左側(cè)的元素2，指針k指向最右側(cè)的元素12：
計(jì)算兩指針對(duì)應(yīng)元素之和，2+12 = 14 > 12，結(jié)果偏大了。
由于數(shù)組是按照升序排列，k左側(cè)的元素一定小于k，因此我們把指針k左移一位：
計(jì)算兩指針對(duì)應(yīng)元素之和，2+9 = 11< 12，這次結(jié)果又偏小了。
j右側(cè)的元素一定大于j，因此我們把指針j右移一位：
計(jì)算兩指針對(duì)應(yīng)元素之和，3+9 = 12，正好符合要求！
因此我們成功找到了一組匹配的組合：1，3，9
但這并不是結(jié)束，我們要繼續(xù)尋找其他組合，讓指針k繼續(xù)左移：
計(jì)算兩指針對(duì)應(yīng)元素之和，3+7 = 10< 12，結(jié)果偏小了。
于是我們讓指針j右移：
計(jì)算兩指針對(duì)應(yīng)元素之和，5+7 = 12，又找到符合要求的一組：
1，5，7
我們繼續(xù)尋找，讓指針k左移：
計(jì)算兩指針對(duì)應(yīng)元素之和，5+6 = 11< 12，結(jié)果偏小了。
于是我們讓指針j右移：
此時(shí)雙指針重合在了一起，如果再繼續(xù)移動(dòng)，就有可能和之前找到的組合重復(fù)，因此我們直接結(jié)束本輪循環(huán)。
第2輪，訪問(wèn)數(shù)組的第2個(gè)元素2，把問(wèn)題轉(zhuǎn)化成從后面元素中找出和為11（13-2）的兩個(gè)數(shù)。
我們?nèi)匀辉O(shè)置兩個(gè)指針，指針j指向剩余元素中最左側(cè)的元素3，指針k指向最右側(cè)的元素12：
計(jì)算兩指針對(duì)應(yīng)元素之和，3+12 = 15 > 11，結(jié)果偏大了。
我們讓指針k左移：
計(jì)算兩指針對(duì)應(yīng)元素之和，3+9 = 12 > 11，結(jié)果仍然偏大。
我們讓指針k繼續(xù)左移：
計(jì)算兩指針對(duì)應(yīng)元素之和，3+7 = 10 < 11，結(jié)果偏小了。
我們讓指針j右移：
計(jì)算兩指針對(duì)應(yīng)元素之和，5+7 = 12 > 11，結(jié)果又偏大了。
我們讓指針k左移：
計(jì)算兩指針對(duì)應(yīng)元素之和，5+6 = 11，于是我們又找到符合要求的一組：
2，5，6
我們繼續(xù)尋找，讓指針k左移：
此時(shí)雙指針又一次重合在一起，我們結(jié)束本輪循環(huán)。
按照這個(gè)思路，我們一直遍歷完整個(gè)數(shù)組。
像這樣利用兩個(gè)指針指向數(shù)組兩端，不斷向中間靠攏調(diào)整來(lái)尋找匹配組合的方法，就是雙指針?lè)?，也被稱為“夾逼法”。
public static List> threeSumv2(int[] nums, int target) {
Arrays.sort(nums);
List> resultList = new ArrayList>();
//大循環(huán)
for (int i = 0; i < nums.length; i++) {
int d = target - nums[i];
// j和k雙指針循環(huán)定位，j在左端，k在右端
for (int j=i+1,k=nums.length-1; j // k指針向左移動(dòng)
while (jd) {
k--;
}
//雙指針重合，跳出本次循環(huán)
if (j == k) {
break;
}
if (nums[j] + nums[k] == d) {
List list = Arrays.asList(nums[i], nums[j], nums[k]);
resultList.add(list);
}
}
}
return resultList;
}
上面這段代碼表面上有三層循環(huán)，但每一輪指針j和k的移動(dòng)次數(shù)加起來(lái)最多n-1次，因此該解法的整體時(shí)間復(fù)雜度是O（n2）。
最關(guān)鍵的是，該解法并沒(méi)有使用額外的集合（排序是直接在輸入數(shù)組上進(jìn)行的），所以空間復(fù)雜度只有O（1）！
—————END—————
喜歡本文的朋友，歡迎關(guān)注公眾號(hào) 程序員小灰，收看更多精彩內(nèi)容
點(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)系我們，謝謝！
下載文檔
