好久沒有水刷算法題的博客了，也不是因?yàn)橐恢睕]寫，而是單個(gè)題目總感覺記錄下來差點(diǎn)意思。正好今天又碰到一個(gè)可以用雙指針來解決的問題，順便記錄一下。
在我看來，雙指針并不是一種“算法”，而是一種解決算法題目的技巧，如果運(yùn)用得當(dāng)其實(shí)可以方便的解決某一種類型的問題。
寫到這里想起來前幾天和基友吹水，關(guān)于鏈表的題目，問就是快慢指針。為什么呢？鏈表相關(guān)的題目有一些比較基礎(chǔ)又比較簡單的都很適合用快慢指針來解決。比如單向鏈表是否有環(huán)，就可以利用快慢指針是否相遇來判斷。再者如秋鏈表的中間項(xiàng)，可以利用快指針步長為2，慢指針步長為1，保證快指針先走來得出結(jié)果。（當(dāng)快指針走到鏈表尾部，奇數(shù)個(gè)項(xiàng)時(shí)，慢指針就是中間點(diǎn)；偶數(shù)個(gè)時(shí)，慢指針指向的就是中間兩個(gè)項(xiàng)的左邊一項(xiàng)。）又或是求倒數(shù)第n個(gè)結(jié)點(diǎn)，就可以“快”指針先走n項(xiàng)，慢指針再走等等。所以看來多總結(jié)相似的解法還是有些好處的。
廢話不扯了，來看幾道題目吧。題目來自于LeetCode，傳送門。
?
11. 盛最多水的容器
給你 n 個(gè)非負(fù)整數(shù) a1，a2，...，an，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn)?(i,?ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i?的兩個(gè)端點(diǎn)分別為?(i,?ai) 和 (i, 0)。找出其中的兩條線，使得它們與?x?軸共同構(gòu)成的容器可以容納最多的水。
說明：你不能傾斜容器，且?n?的值至少為 2。
圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為?49。
?
示例：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
如果你和我一樣，一開始沒想起使用雙指針來解決這個(gè)問題的話，可能會(huì)感覺比較困擾。因?yàn)榘凑疹}目的要求，我們實(shí)際上是求得最大的面積。而這個(gè)面積又受兩個(gè)變量影響，一是高度二是長度。而當(dāng)我們確定一個(gè)面積之后，如果要去判斷下一個(gè)面積是不是更大就需要移動(dòng)“水桶的一邊”，這可能會(huì)導(dǎo)致長度和高度都發(fā)生變化。進(jìn)而與暴力求解法沒什么差別了。
當(dāng)然如果再仔細(xì)一點(diǎn)其實(shí)會(huì)發(fā)現(xiàn)，關(guān)于高度，最大面積只受兩邊高度中最矮的那個(gè)影響，傳說中的木桶效應(yīng)嘛~~。這樣我們不妨就拿數(shù)組的兩個(gè)邊界作為木桶的兩邊，來計(jì)算一個(gè)初始的面積。這樣做的好處是“長度”已經(jīng)是最大值了，接下來如果我們要移動(dòng)某一條邊，發(fā)現(xiàn)移動(dòng)后的高度還不高于移動(dòng)前的高度，我們可以直接說它的面積是會(huì)比移動(dòng)前更小的。并且，由于“木桶效應(yīng)”，我們也可以推斷每次都應(yīng)該移動(dòng)最矮的那條邊。(如果移動(dòng)的是高的邊，那么木桶的長度一定比之前小，高度一定不大于之前的高度，故面積一定比之前小)。
看看Code吧。
1 public class Solution { 2 public int MaxArea(int[] height) { 3 int begin = 0; 4 int end = height.Length - 1; 5 6 int result = -1; 7 8 while(begin < end) 9 {10 int temp;11 if(height[begin] > height[end])12 {13 temp = (end-begin) * height[end];14 end --;15 }16 else17 {18 temp = (end-begin) * height[begin];19 begin ;20 }21 22 result = temp > result ? temp : result;23 }24 25 return result;26 }27 }官方解法有關(guān)于應(yīng)該移動(dòng)哪條邊更詳細(xì)的證明，傳送門。
?
15. 三數(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]
]
?
對(duì)于原始的數(shù)組，看起來似乎只能使用暴力求解。但如果它是有序的呢，畢竟要求三個(gè)數(shù)字和為0，如果是有序數(shù)組應(yīng)該可以省去一些邊界值的情況，減少比較的次數(shù)。
假設(shè)我們按索引的順序選取a，b，c。如果數(shù)組是有序的，那么可以推斷如果a>0或a b>0,那么一定不存在這樣的結(jié)果。所以我們可以從索引為0的位置讓a開始遍歷，然后第二個(gè)數(shù)字b選取a的下一位，c選取數(shù)組的末尾。這樣根據(jù)a b c與0的大小比較，就可以知道我們當(dāng)前的值應(yīng)該進(jìn)行怎樣的調(diào)整。如果較大，我們就移動(dòng)c，讓和變小。如果較小。我們就移動(dòng)b，讓和變大。
Show code:
1 public class Solution { 2 public IList<IList<int>> ThreeSum(int[] nums) 3 { 4 List<IList<int>> result = new List<IList<int>>(); 5 6 if (nums.Length < 3) 7 { 8 return result; 9 }10 11 Array.Sort(nums);12 13 for(int i = 0; i < nums.Length - 2; i )14 {15 int k = i;16 int m = i 1;17 int n = nums.Length - 1;18 19 while (m < n)20 {21 if (nums[k] > 0)22 break;23 24 if (nums[k] nums[m] nums[n] == 0)25 {26 var temp = new List<int>();27 temp.Add(nums[k]);28 temp.Add(nums[m]);29 temp.Add(nums[n]);30 31 result.Add(temp);32 33 do34 {35 n--;36 }37 while (n > m && nums[n] == nums[n 1]);38 39 do40 {41 m ;42 }43 while (m < n && nums[m] == nums[m - 1]);44 }45 else if (nums[k] nums[m] nums[n] > 0)46 {47 do48 {49 n--;50 }51 while (n > m && nums[n] == nums[n 1]);52 }53 else54 {55 do56 {57 m ;58 }59 while (m < n && nums[m] == nums[m - 1]);60 }61 }62 63 do64 {65 i ;66 }67 while (i < nums.Length && nums[i] == nums[i - 1]);68 69 i--;70 }71 72 return result;73 }74 }感興趣的小伙伴也可以去搜索一些這道題目下別的解法。只能說大神實(shí)在是太厲害了，哈哈。
?
16. 最接近的三數(shù)之和
給定一個(gè)包括?n 個(gè)整數(shù)的數(shù)組?nums?和 一個(gè)目標(biāo)值?target。找出?nums?中的三個(gè)整數(shù)，使得它們的和與?target?最接近。返回這三個(gè)數(shù)的和。假定每組輸入只存在唯一答案。
例如，給定數(shù)組 nums = [-1，2，1，-4], 和 target = 1.
與 target 最接近的三個(gè)數(shù)的和為 2. (-1 2 1 = 2).
這道題和前面一道有一點(diǎn)點(diǎn)區(qū)別，不是相等，而是最接近。因此需要利用絕對(duì)值來進(jìn)行判斷。主要需要改變的地方是需要記錄一下當(dāng)前絕對(duì)值，如果不是需要更新，來幫助我們找到最接近的值。
上代碼：
1 public class Solution { 2 public int ThreeSumClosest(int[] nums, int target) 3 { 4 int ans = nums[0] nums[1] nums[2]; 5 6 var sortNums = nums.OrderBy(x => x).ToArray(); 7 8 for (int i = 0; i < sortNums.Count() - 2; i ) 9 {10 int start = i 1;11 int end = sortNums.Count() - 1;12 13 while (start < end)14 {15 int temp = sortNums[i] sortNums[start] sortNums[end];16 if (Math.Abs(temp - target) < Math.Abs(ans - target))17 {18 ans = temp;19 }20 21 if (temp > target)22 {23 end--;24 }25 else if (temp < target)26 {27 start ;28 }29 else30 {31 return target;32 }33 }34 35 }36 37 return ans;38 }39 }?
嗯，算法還是要多多練習(xí)呀。
來源：https://www.icode9.com/content-4-691901.html聯(lián)系客服
