兩數之和

題目描述：

給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，并返回他們的數組下標。  

你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。  

示例:

給定 nums = [2, 7, 11, 15], target = 9  

因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]  

題目很容易理解，即讓查看數組中有沒有兩個數的和為目標數，如果有的話則返回兩數下標，在這為大家提供兩種解法雙指針（暴力）法，和哈希表法，大家可以看一下。

哈希表法 

解析

 

是不是很容易理解，下面我們來看一下題目代碼。 

題目代碼：

     

雙指針（暴力）法 

解析

雙指針（L,R）法的思路很簡單，L指針用來指向第一個值，R指針用來從L指針的后面查找數組中是否含有和L指針指向值的和為目標值的數。見下圖

例：綠指針指向的值為3，藍指針需要在綠指針的后面遍歷查找是否含有 target - 3  的元素即 5 - 3 = 2，若含有返回即可。

    

題目代碼

     

三數之和 

題目描述：

給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復的三元組。  

注意：答案中不可以包含重復的三元組。  

示例：

給定數組 nums = [-1, 0, 1, 2, -1, -4]，  

滿足要求的三元組集合為：[ [-1, 0, 1], [-1, -1, 2] ]  

這個題目算是對剛才題目的升級，剛才題目我們是只需返回一個例子即可，但是這個題目是讓我們返回所有情況，這個題目我們需要返回三個數相加為 0 的所有情況，但是我們需要去掉重復的三元組(算是該題的核心)，所以這個題目還是挺有趣的，大家記得打卡呀。

哈希表法

解析

我們這個題目的哈希表解法是很容易理解的，我們首先將數組排序，排序之后我們將排序過的元素存入哈希表中，然后我們首先通過兩層遍歷，確定好前兩個數字，那么我們只需要哈希表是否存在符合情況的第三個數字即可，跟暴力解法的思路類似，很容易理解，但是這里我們需要注意的情況就是，例如我們的例子為[-2 , 1 , 1],如果我們完全按照以上思路來的話，則會出現兩個解，[-2 , 1 , 1]和[1 , 1, -2]。具體原因為，確定 -2，1之后發現 1 在哈希表中，存入。確定 1 ，1 之后發現 -2 在哈希表中，存入。所以我們需要加入一個約束避免這種情況，那就是我們第三個數的索引大于第二個數時才存入。

 

上面這種情況時是不可以存入的，因為我們雖然在哈希表中找到了符合要求的值，但是 -2 的索引為 0 小于 2 所以不可以存入。

題目代碼

     

多指針 

解析：

如果我們將上個題目的指針解法稱做是雙指針的話，那么這個題目用到的方法就是三指針，因為我們是三數之和嘛，一個指針對應一個數，下面我們看一下具體思路，其實原理很簡單，我們先將數組排序，直接 Arrays.sort() 解決，排序之后處理起來就很容易了。下面我們來看下三個指針的初始位置。

 

初始情況見上圖，我們看當前情況，三數之和為  -3  ，很顯然不是 0 ，那么我們應該怎么做呢？

我們設想一下，我們當前的三數之和為 -3 < 0 那么我們如果移動橙色指針的話則會讓我們的三數之和變的更小，因為我們的數組是有序的，所以我們移動橙色指針（藍色不動）時和會變小，如果移動藍色指針（橙色不動）的話，三數之和則會變大，所以這種情況則需要向右移動我們的藍色指針，找到三數之和等于 0 的情況進行保存，如果三數之和大于 0 的話，則需要移動橙色指針，途中有三數之和為 0 的情況則保存。直至藍橙兩指針相遇跳出該次循環，然后我們的綠指針右移一步，繼續執行上訴步驟。但是這里我們需要注意的一個細節就是，我們需要去除相同三元組的情況，我們看下面的例子。

 

這里我們發現 0 - 1 + 1 = 0，當前情況是符合的，所以我們需要存入該三元組，存入后，藍色指針向后移動一步，橙色指針向前移動一步，我們發現仍為 0 -1 + 1 = 0 仍然符合，但是如果繼續存入該三元組的話則不符合題意，所以我們需要去重。這里可以借助HashSet但是效率太差，不推薦。這里我們可以使用 while 循環將藍色指針移動到不和剛才相同的位置，也就是直接移動到元素 0 上，橙色指針同樣也是。則是下面這種情況，這樣我們就實現了去重，然后繼續判斷當前三數之和是否為 0 。

 

動圖解析：

 

題目代碼：

     

四數之和 

題目描述

給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復的四元組。  

注意：  

答案中不可以包含重復的四元組。  

示例：

給定數組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。  

滿足要求的四元組集合為：[ [-1,  0, 0, 1], [-2, -1, 1, 2], [-2,  0, 0, 2] ]  

我們已經完成了兩數之和和三數之和，這個題目應該就手到擒來了，因為我們已經知道這類題目的解題框架，兩數之和呢，我們就先固定第一個數 ，然后移動指針去找第二個符合的，三數之和，固定一個數，雙指針去找符合情況的其他兩位數，那么我們四數之和，也可以先固定兩個數，然后利用雙指針去找另外兩位數。所以我們來搞定他吧。 

多指針： 

解析：

三數之和是，我們首先確定一個數，然后利用雙指針去找另外的兩個數，我們在這個題目里面的解題思路是需要首先確定兩個數然后利用雙指針去找另外兩個數，和三數之和思路基本一致很容易理解。我們具體思路可以參考下圖。

這里需要注意的是，我們的  target  不再和三數之和一樣為  0 ，target  是不固定的，所以解題思路不可以完全照搬上面的題目。另外這里也需要考慮去重的情況，思路和上題一致。

 

上圖則為我們查找到一個符合條件的四元組的情況，查找成功之后，下一步移動藍色指針，重新定義綠藍指針，繼續執行上面步驟。

 

動圖解析：

 

題目代碼：