前一段時間，算法數小灰分別講解了兩道leecode上的題兩經典算法題：
漫畫：如何在數組中找到和為 “特定值” 的兩個數？
漫畫：如何在數組中找到和為 “特定值” 的三個數？
今天，小灰把這兩道題整合起來，和數并修改了其中的漫畫細節問題，感謝大家的算法數指正。
————— 第二天 —————
什么意思呢？我們來舉個例子，題兩給定下面這樣一個整型數組（假定數組不存在重復元素）：
我們隨意選擇一個特定值，和數比如13，漫畫要求找出兩數之和等于13的算法數全部組合。
由于12+1 = 13，題兩6+7 = 13，所以最終的輸出結果（輸出的是下標）如下：
【1， 6】
【2， 7】
小灰想表達的思路，是直接遍歷整個數組，每遍歷到一個元素，就和其他元素相加，看看和是不是等于那個特定值。
第1輪，用元素5和其他元素相加：
沒有找到符合要求的兩個元素。
第2輪，用元素12和其他元素相加：
發現12和1相加的結果是13，符合要求。
按照這個思路，一直遍歷完整個數組。
————————————
讓我們來具體演示一下：
第1輪，訪問元素5，計算出13-5=8。在哈希表中查找8，發現查不到：
第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 < 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)));
//為防止找到重復的元素對，匹配后從哈希表刪除對應元素
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;
} 舉個例子，給定下面這樣一個整型數組（假定數組不存在重復元素）：
我們隨意選擇一個特定值，比如13，要求找出三數之和等于13的全部組合。
由于5+6+2=13， 5+1+7=13，3+9+1=13，所以最終的輸出結果如下（直接輸出元素值即可）：
【5， 6，2】
【5， 1，7】
【3， 9，1】
小灰的思路，是把原本的“三數之和問題”，轉化成求n次“兩數之和問題”。
我們以上面這個數組為例，選擇特定值13，演示一下小灰的具體思路：
第1輪，訪問數組的第1個元素5，把問題轉化成從后面元素中找出和為8（13-5）的兩個數：
如何找出和為8的兩個數呢？按照上一次所講的，我們可以使用哈希表高效求解：
第2輪，訪問數組的第2個元素12，把問題轉化成從后面元素中找出和為1（13-12）的兩個數：
第3輪，訪問數組的第3個元素6，把問題轉化成從后面元素中找出和為7（13-6）的兩個數：
以此類推，一直遍歷完整個數組，相當于求解了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];
//尋找兩數之和等于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;
}
在上面的代碼中，每一輪解決“兩數之和問題”的時間復雜度是O（n），一共迭代n輪，所以該解法總的時間復雜度是O（n2）。
至于空間復雜度，同一個哈希表被反復構建，哈希表中最多有n-1個鍵值對，所以該解法的空間復雜度是O（n）。
我們仍然以之前的數組為例，對數組進行升序排列：
這樣說起來有些抽象，我們來具體演示一下：
第1輪，訪問數組的第1個元素1，把問題轉化成從后面元素中找出和為12（13-1）的兩個數。
如何找出和為12的兩個數呢？我們設置兩個指針，指針j指向剩余元素中最左側的元素2，指針k指向最右側的元素12：
計算兩指針對應元素之和，2+12 = 14 > 12，結果偏大了。
由于數組是按照升序排列，k左側的元素一定小于k，因此我們把指針k左移一位：
計算兩指針對應元素之和，2+9 = 11< 12，這次結果又偏小了。
j右側的元素一定大于j，因此我們把指針j右移一位：
計算兩指針對應元素之和，3+9 = 12，正好符合要求！
因此我們成功找到了一組匹配的組合：1，3，9
但這并不是結束，我們要繼續尋找其他組合，讓指針k繼續左移：
計算兩指針對應元素之和，3+7 = 10< 12，結果偏小了。
于是我們讓指針j右移：
計算兩指針對應元素之和，5+7 = 12，又找到符合要求的一組：
1，5，7
我們繼續尋找，讓指針k左移：
計算兩指針對應元素之和，5+6 = 11< 12，結果偏小了。
于是我們讓指針j右移：
此時雙指針重合在了一起，如果再繼續移動，就有可能和之前找到的組合重復，因此我們直接結束本輪循環。
第2輪，訪問數組的第2個元素2，把問題轉化成從后面元素中找出和為11（13-2）的兩個數。
我們仍然設置兩個指針，指針j指向剩余元素中最左側的元素3，指針k指向最右側的元素12：
計算兩指針對應元素之和，3+12 = 15 > 11，結果偏大了。
我們讓指針k左移：
計算兩指針對應元素之和，3+9 = 12 > 11，結果仍然偏大。
我們讓指針k繼續左移：
計算兩指針對應元素之和，3+7 = 10 < 11，結果偏小了。
我們讓指針j右移：
計算兩指針對應元素之和，5+7 = 12 > 11，結果又偏大了。
我們讓指針k左移：
計算兩指針對應元素之和，5+6 = 11，于是我們又找到符合要求的一組：
2，5，6
我們繼續尋找，讓指針k左移：
此時雙指針又一次重合在一起，我們結束本輪循環。
按照這個思路，我們一直遍歷完整個數組。
像這樣利用兩個指針指向數組兩端，不斷向中間靠攏調整來尋找匹配組合的方法，就是雙指針法，也被稱為“夾逼法”。
public static List> threeSumv2(int[] nums, int target) {
Arrays.sort(nums);
List> resultList = new ArrayList>();
//大循環
for (int i = 0; i < nums.length; i++) {
int d = target - nums[i];
// j和k雙指針循環定位，j在左端，k在右端
for (int j=i+1,k=nums.length-1; j // k指針向左移動
while (jd) {
k--;
}
//雙指針重合，跳出本次循環
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;
}
上面這段代碼表面上有三層循環，但每一輪指針j和k的移動次數加起來最多n-1次，因此該解法的整體時間復雜度是O（n2）。
最關鍵的是，該解法并沒有使用額外的集合（排序是直接在輸入數組上進行的），所以空間復雜度只有O（1）！
—————END—————
喜歡本文的朋友，歡迎關注公眾號 程序員小灰，收看更多精彩內容
點個[在看]，是對小灰最大的支持！
免責聲明：本文內容由21ic獲得授權后發布，版權歸原作者所有，本平臺僅提供信息存儲服務。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯系我們，謝謝！
