雙指針解決力扣兩／三數(shù)之和問題

文章目錄

• 雙指針解決力扣兩／三數(shù)之和問題
• • 一、問題描述
  • 二、分析
  • • 1.暴力
    • 2.排序+雙指針法
    • 3.hash法
  • 三、問題描述
  • 四、分析
  • • 方法一：排序 + 雙指針
  • 五、代碼

一、問題描述

二、分析

1.暴力

暴力算法時(shí)間復(fù)雜度O（n2），空間復(fù)雜度O（1）

class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> ans;for(int i = 0;i < nums.size();i++){for(int j = i + 1;j < nums.size();j++){if(nums[i] + nums[j] == target){ans.push_back(i);ans.push_back(j);return ans;}}}return ans;} };

2.排序+雙指針法

• 這里先將數(shù)組排序好O（nlogn），再利用雙指針法遍歷一遍O（n）得到結(jié)果。
• 為了保存下標(biāo)信息另開了一個(gè)數(shù)組
• 時(shí)間復(fù)雜度O（nlogn），空間復(fù)雜度O（n）

class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> ret(2);vector<int> temp(nums);sort(nums.begin(),nums.end());int left = 0;int right = nums.size() - 1;while(left < right){if(nums[left] + nums[right] == target){int flag = 1;for(size_t i = 0;i < temp.size();i++){if(temp[i] == nums[left] && flag){ret[0] = i;flag = 0;}else if(temp[i] == nums[right]){ret[1] = i;}}break;}else if(nums[left] + nums[right] > target){right--;}else {left++;}}return ret;} };

3.hash法

• 利用map數(shù)組構(gòu)造映射，遍歷nums[i]時(shí)，看target-nums[i]是否存在hash表中即可
• 時(shí)間復(fù)雜度O（n），空間復(fù)雜度O（n）

class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> ans;map<int,int>hashmap;for(int i = 0;i < nums.size();i++){if(hashmap[target - nums[i]] && hashmap[target - nums[i]] != i + 1){//防止利用同個(gè)元素ans.push_back(i);ans.push_back(hashmap[target - nums[i]] - 1);return ans;}hashmap[nums[i]] = i + 1;//將hash表對(duì)應(yīng)下標(biāo)＋1，防止處理下標(biāo)為0的情況}return ans;} };

三、問題描述

四、分析

• 本題與 兩數(shù)之和 類似，是非常經(jīng)典的面試題，但是做法不盡相同。

方法一：排序 + 雙指針

• 題目中要求找到所有「不重復(fù)」且和為 0 的三元組，這個(gè)「不重復(fù)」的要求使得我們無法簡單地使用三重循環(huán)枚舉所有的三元組。

這是因?yàn)樵谧顗牡那闆r下，數(shù)組中的元素全部為 0，即

[0, 0, 0, 0, 0, …, 0, 0, 0]

• 任意一個(gè)三元組的和都為 0。如果我們直接使用三重循環(huán)枚舉三元組，會(huì)得到 $O(N^3)$個(gè)滿足題目要求的三元組（其中 N 是數(shù)組的長度）時(shí)間復(fù)雜度至少為 $O(N^3)$
• 在這之后，我們還需要使用哈希表進(jìn)行去重操作，得到不包含重復(fù)三元組的最終答案，又消耗了大量的空間。
• 這個(gè)做法的時(shí)間復(fù)雜度和空間復(fù)雜度都很高，因此我們要換一種思路來考慮這個(gè)問題。
• 「不重復(fù)」的本質(zhì)是什么？我們保持三重循環(huán)的大框架不變，只需要保證：
• 第二重循環(huán)枚舉到的元素不小于當(dāng)前第一重循環(huán)枚舉到的元素；
• 第三重循環(huán)枚舉到的元素不小于當(dāng)前第二重循環(huán)枚舉到的元素。
• 也就是說，我們枚舉的三元組 (a, b, c)滿足a≤b≤c，保證了只有 (a, b, c)這個(gè)順序會(huì)被枚舉到，而 (b, a, c)、(c, b, a)等等這些不會(huì)，這樣就減少了重復(fù)。
• 要實(shí)現(xiàn)這一點(diǎn)，我們可以將數(shù)組中的元素從小到大進(jìn)行排序，隨后使用普通的三重循環(huán)就可以滿足上面的要求。
• 同時(shí)，對(duì)于每一重循環(huán)而言，相鄰兩次枚舉的元素不能相同，否則也會(huì)造成重復(fù)。舉個(gè)例子，如果排完序的數(shù)組為

[0, 1, 2, 2, 2, 3]

• 我們使用三重循環(huán)枚舉到的第一個(gè)三元組為(0,1,2)，如果第三重循環(huán)繼續(xù)枚舉下一個(gè)元素，那么仍然是三元組(0,1,2)，產(chǎn)生了重復(fù)。
• 因此我們需要將第三重循環(huán)「跳到」下一個(gè)不相同的元素，即數(shù)組中的最后一個(gè)元素 3，枚舉三元組 (0, 1, 3)。
• 下面給出了改進(jìn)的方法的偽代碼實(shí)現(xiàn)：

nums.sort() for first = 0 .. n-1// 只有和上一次枚舉的元素不相同，我們才會(huì)進(jìn)行枚舉if first == 0 or nums[first] != nums[first-1] thenfor second = first+1 .. n-1if second == first+1 or nums[second] != nums[second-1] thenfor third = second+1 .. n-1if third == second+1 or nums[third] != nums[third-1] then// 判斷是否有 a+b+c==0check(first, second, third)

• 這種方法的時(shí)間復(fù)雜度仍然為 O(N^3),畢竟我們還是沒有跳出三重循環(huán)的大框架。
• 然而它是很容易繼續(xù)優(yōu)化的，可以發(fā)現(xiàn)，如果我們固定了前兩重循環(huán)枚舉到的元素 a 和 b，那么只有唯一的 c 滿足 a+b+c=0。
• 當(dāng)?shù)诙匮h(huán)往后枚舉一個(gè)元素 b'時(shí)，由于 b’ > b ;那么滿足 a+b’+c’=0的 c' 一定有 c' < c,即 c'在數(shù)組中一定出現(xiàn)在 c 的左側(cè)。
• 也就是說，我們可以從小到大枚舉 b，同時(shí)從大到小枚舉 c，即第二重循環(huán)和第三重循環(huán)實(shí)際上是并列的關(guān)系。
• 有了這樣的發(fā)現(xiàn)，我們就可以保持第二重循環(huán)不變，而將第三重循環(huán)變成一個(gè)從數(shù)組最右端開始向左移動(dòng)的指針，從而得到下面的偽代碼：

nums.sort() for first = 0 .. n-1if first == 0 or nums[first] != nums[first-1] then// 第三重循環(huán)對(duì)應(yīng)的指針third = n-1for second = first+1 .. n-1if second == first+1 or nums[second] != nums[second-1] then// 向左移動(dòng)指針，直到 a+b+c 不大于 0while nums[first]+nums[second]+nums[third] > 0third = third-1// 判斷是否有 a+b+c==0check(first, second, third)

• 這個(gè)方法就是我們常說的「雙指針」，當(dāng)我們需要枚舉數(shù)組中的兩個(gè)元素時(shí)，如果我們發(fā)現(xiàn)隨著第一個(gè)元素的遞增，第二個(gè)元素是遞減的，那么就可以使用雙指針的方法，將枚舉的時(shí)間復(fù)雜度從O(N^2) 減少至 O(N)。
• 為什么是 O(N)呢？這是因?yàn)樵诿杜e的過程每一步中，「左指針」會(huì)向右移動(dòng)一個(gè)位置（也就是題目中的 b），而「右指針」會(huì)向左移動(dòng)若干個(gè)位置，這個(gè)與數(shù)組的元素有關(guān)，但我們知道它一共會(huì)移動(dòng)的位置數(shù)為 O(N)，均攤下來，每次也向左移動(dòng)一個(gè)位置，因此時(shí)間復(fù)雜度為 O(N)。
• 注意到我們的偽代碼中還有第一重循環(huán)，時(shí)間復(fù)雜度為 O(N)O(N)，因此枚舉的總時(shí)間復(fù)雜度為 O(N^2)
• 由于排序的時(shí)間復(fù)雜度為 O(NlogN)，在漸進(jìn)意義下小于前者，因此算法的總時(shí)間復(fù)雜度為 O(N^2)
• 上述的偽代碼中還有一些細(xì)節(jié)需要補(bǔ)充，例如我們需要保持左指針一直在右指針的左側(cè)（即滿足 b≤c），具體可以參考下面的代碼，均給出了詳細(xì)的注釋。

五、代碼

class Solution { public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());vector<vector<int>> ans;// 枚舉 afor (int first = 0; first < n; ++first) {// 需要和上一次枚舉的數(shù)不相同if (first > 0 && nums[first] == nums[first - 1]) {continue;}// c 對(duì)應(yīng)的指針初始指向數(shù)組的最右端int third = n - 1;int target = -nums[first];// 枚舉 bfor (int second = first + 1; second < n; ++second) {// 需要和上一次枚舉的數(shù)不相同if (second > first + 1 && nums[second] == nums[second - 1]) {continue;}// 需要保證 b 的指針在 c 的指針的左側(cè)while (second < third && nums[second] + nums[third] > target) {--third;}// 如果指針重合，隨著 b 后續(xù)的增加// 就不會(huì)有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出循環(huán)if (second == third) {break;}if (nums[second] + nums[third] == target) {ans.push_back({nums[first], nums[second], nums[third]});}}}return ans;} }; 超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的双指针解决力扣两／三数之和问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。