建站
咨詢
售后
建站咨詢
新聞中心
今天為大家?guī)砣狼蠛蛦栴}，通過文字，圖畫，動(dòng)圖為大家解析，很容易就能讀懂，每道題目都是經(jīng)典題，大家快來打卡吧。
網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、小程序設(shè)計(jì)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了七里河免費(fèi)建站歡迎大家使用！
題目來源：leetcode 1.兩數(shù)之和(簡單) 15.三數(shù)之和(中等) 18.四數(shù)之和(中等)
兩數(shù)之和
題目描述：
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素不能使用兩遍。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
題目很容易理解，即讓查看數(shù)組中有沒有兩個(gè)數(shù)的和為目標(biāo)數(shù)，如果有的話則返回兩數(shù)下標(biāo)，在這為大家提供兩種解法雙指針(暴力)法，和哈希表法，大家可以看一下。
哈希表法
解析
哈希表的做法很容易理解，我們只需通過一次循環(huán)即可，假如我們的 target 值為 9，當(dāng)前指針指向的值為 2 ，我們只需從哈希表中查找是否含有 7，因?yàn)? - 2 =7 。如果含有 7 我們直接返回即可，如果不含有則將當(dāng)前的2存入哈希表中，指針移動(dòng)，指向下一元素。注：key 為元素值，value 為元素索引。
動(dòng)圖解析：
是不是很容易理解，下面我們來看一下題目代碼。
題目代碼：
雙指針(暴力)法
解析
雙指針(L,R)法的思路很簡單，L指針用來指向第一個(gè)值，R指針用來從L指針的后面查找數(shù)組中是否含有和L指針指向值的和為目標(biāo)值的數(shù)。見下圖
例：綠指針指向的值為3，藍(lán)指針需要在綠指針的后面遍歷查找是否含有 target - 3 的元素即 5 - 3 = 2，若含有返回即可。
題目代碼
三數(shù)之和
題目描述：
給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ?請(qǐng)你找出所有滿足條件且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
示例：
給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：[ [-1, 0, 1], [-1, -1, 2] ]
這個(gè)題目算是對(duì)剛才題目的升級(jí)，剛才題目我們是只需返回一個(gè)例子即可，但是這個(gè)題目是讓我們返回所有情況，這個(gè)題目我們需要返回三個(gè)數(shù)相加為 0 的所有情況，但是我們需要去掉重復(fù)的三元組(算是該題的核心)，所以這個(gè)題目還是挺有趣的，大家記得打卡呀。
哈希表法
解析
我們這個(gè)題目的哈希表解法是很容易理解的，我們首先將數(shù)組排序，排序之后我們將排序過的元素存入哈希表中，然后我們首先通過兩層遍歷，確定好前兩個(gè)數(shù)字，那么我們只需要哈希表是否存在符合情況的第三個(gè)數(shù)字即可，跟暴力解法的思路類似，很容易理解，但是這里我們需要注意的情況就是，例如我們的例子為[-2 , 1 , 1],如果我們完全按照以上思路來的話，則會(huì)出現(xiàn)兩個(gè)解，[-2 , 1 , 1]和[1 , 1, -2]。具體原因?yàn)椋_定 -2，1之后發(fā)現(xiàn) 1 在哈希表中，存入。確定 1 ，1 之后發(fā)現(xiàn) -2 在哈希表中，存入。所以我們需要加入一個(gè)約束避免這種情況，那就是我們第三個(gè)數(shù)的索引大于第二個(gè)數(shù)時(shí)才存入。
上面這種情況時(shí)是不可以存入的，因?yàn)槲覀冸m然在哈希表中找到了符合要求的值，但是 -2 的索引為 0 小于 2 所以不可以存入。
題目代碼
多指針
解析：
如果我們將上個(gè)題目的指針解法稱做是雙指針的話，那么這個(gè)題目用到的方法就是三指針，因?yàn)槲覀兪侨龜?shù)之和嘛，一個(gè)指針對(duì)應(yīng)一個(gè)數(shù)，下面我們看一下具體思路，其實(shí)原理很簡單，我們先將數(shù)組排序，直接 Arrays.sort() 解決，排序之后處理起來就很容易了。下面我們來看下三個(gè)指針的初始位置。
初始情況見上圖，我們看當(dāng)前情況，三數(shù)之和為 -3 ，很顯然不是 0 ，那么我們應(yīng)該怎么做呢?
我們?cè)O(shè)想一下，我們當(dāng)前的三數(shù)之和為 -3 < 0 那么我們?nèi)绻苿?dòng)橙色指針的話則會(huì)讓我們的三數(shù)之和變的更小，因?yàn)槲覀兊臄?shù)組是有序的，所以我們移動(dòng)橙色指針(藍(lán)色不動(dòng))時(shí)和會(huì)變小，如果移動(dòng)藍(lán)色指針(橙色不動(dòng))的話，三數(shù)之和則會(huì)變大，所以這種情況則需要向右移動(dòng)我們的藍(lán)色指針，找到三數(shù)之和等于 0 的情況進(jìn)行保存，如果三數(shù)之和大于 0 的話，則需要移動(dòng)橙色指針，途中有三數(shù)之和為 0 的情況則保存。直至藍(lán)橙兩指針相遇跳出該次循環(huán)，然后我們的綠指針右移一步，繼續(xù)執(zhí)行上訴步驟。但是這里我們需要注意的一個(gè)細(xì)節(jié)就是，我們需要去除相同三元組的情況，我們看下面的例子。
這里我們發(fā)現(xiàn) 0 - 1 + 1 = 0，當(dāng)前情況是符合的，所以我們需要存入該三元組，存入后，藍(lán)色指針向后移動(dòng)一步，橙色指針向前移動(dòng)一步，我們發(fā)現(xiàn)仍為 0 -1 + 1 = 0 仍然符合，但是如果繼續(xù)存入該三元組的話則不符合題意，所以我們需要去重。這里可以借助HashSet但是效率太差，不推薦。這里我們可以使用 while 循環(huán)將藍(lán)色指針移動(dòng)到不和剛才相同的位置，也就是直接移動(dòng)到元素 0 上，橙色指針同樣也是。則是下面這種情況，這樣我們就實(shí)現(xiàn)了去重，然后繼續(xù)判斷當(dāng)前三數(shù)之和是否為 0 。
動(dòng)圖解析：
題目代碼：
四數(shù)之和
題目描述
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums 和一個(gè)目標(biāo)值 target，判斷 nums 中是否存在四個(gè)元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等?找出所有滿足條件且不重復(fù)的四元組。
注意：
答案中不可以包含重復(fù)的四元組。
示例：
給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
滿足要求的四元組集合為：[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
我們已經(jīng)完成了兩數(shù)之和和三數(shù)之和，這個(gè)題目應(yīng)該就手到擒來了，因?yàn)槲覀円呀?jīng)知道這類題目的解題框架，兩數(shù)之和呢，我們就先固定第一個(gè)數(shù) ，然后移動(dòng)指針去找第二個(gè)符合的，三數(shù)之和，固定一個(gè)數(shù)，雙指針去找符合情況的其他兩位數(shù)，那么我們四數(shù)之和，也可以先固定兩個(gè)數(shù)，然后利用雙指針去找另外兩位數(shù)。所以我們來搞定他吧。
多指針：
解析：
三數(shù)之和是，我們首先確定一個(gè)數(shù)，然后利用雙指針去找另外的兩個(gè)數(shù)，我們?cè)谶@個(gè)題目里面的解題思路是需要首先確定兩個(gè)數(shù)然后利用雙指針去找另外兩個(gè)數(shù)，和三數(shù)之和思路基本一致很容易理解。我們具體思路可以參考下圖。
這里需要注意的是，我們的 target 不再和三數(shù)之和一樣為 0 ，target 是不固定的，所以解題思路不可以完全照搬上面的題目。另外這里也需要考慮去重的情況，思路和上題一致。
上圖則為我們查找到一個(gè)符合條件的四元組的情況，查找成功之后，下一步移動(dòng)藍(lán)色指針，重新定義綠藍(lán)指針，繼續(xù)執(zhí)行上面步驟。
動(dòng)圖解析：
題目代碼：
四數(shù)之和
本文轉(zhuǎn)載自微信公眾號(hào)「 袁廚的算法小屋」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系 袁廚的算法小屋公眾號(hào)。
網(wǎng)頁題目：一文把三個(gè)經(jīng)典求和問題吃的透透滴
分享路徑：http://m.5511xx.com/article/dhopsis.html
