前言

本專欄的上篇，講述了雙指針的一些基礎的算法習題
今天我們來學習更進一步的雙指針用法吧
其實也是大相徑庭，和前面的差不多，只不過題目難了一些
fellow me

有效的三角形個數

有效的三角形個數

思路

第一種解法就是——暴力求解（會超時）
三層 for 循環枚舉出所有的三元組，并且判斷是否能構成三角形。
雖然說是暴力求解，但是還是想優化一下：
判斷三角形的優化：
如果能構成三角形，需要滿足任意兩邊之和要大于第三邊。但是實際上只需讓較小的兩條邊之和大于第三邊即可。
因此我們可以先將原數組排序，然后從小到大枚舉三元組，一方面省去枚舉的數量，另一方面方便判斷是否能構成三角形。
第二種解法就是——雙指針
根據「解法一」中的優化思想，我們可以固定一個「最長邊」，然后在比這條邊小的有序數組中找出一個二元組，使這個二元組之和大于這個最長邊。由于數組是有序的，我們可以利用**「對撞指針」來優化。
先給數組排序，然后從右邊開始指定一個數**，再在這個數的左邊區間定義 left 和 right 指針進行對撞
如果 nums[left] + nums[right] > nums[i] ：說明 [left, right - 1] 區間上的所有元素均可以與 nums[right] 構成比nums[i] 大的二元組
滿足條件的有 right - left 種
此時 right 位置的元素的所有情況相當于全部考慮完畢， right-- ，進入下一輪判斷
如果 nums[left] + nums[right] <= nums[i] ：
說明 left 位置的元素是不可能與 [left + 1, right] 位置上的元素構成滿足條件的二元組
left 位置的元素可以舍去， left++ 進入下輪循環

話不多說上代碼吧

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

查找總價格為目標值的兩個商品

查找總價格為目標值的兩個商品

思路

解法一肯定還是暴力解法，但是超時是不可避免的
就是兩層for循環遍歷就好啦
解法二我們使用雙指針
初始化 left ， right 分別指向數組的左右兩端（這里不是我們理解的指針，而是數組的下標）
當 left < right 的時候，一直循環
當 nums[left] + nums[right] == target 時，說明找到結果，記錄結果，并且返回；
當 nums[left] + nums[right] < target 時：
對于 nums[left] 而言，此時 nums[right] 相當于是 nums[left] 能碰到的最大值（別忘了，這里是升序數組哈~）。如果此時不符合要求，說明在這個數組里面，沒有別的數符合 nums[left] 的要求了（最大的數都滿足不了你，你已經沒救了）。
因此，我們可以大膽舍去這個數，讓 left++ ，去比較下一組數據；
那對于 nums[right] 而言，由于此時兩數之和是小于目標值的， nums[right]還可以選擇比 nums[left] 大的值繼續努力達到目標值，因此 right 指針我們按兵不動；
當 nums[left] + nums[right] > target 時，同理我們可以舍去nums[right] （最小的數都滿足不了你，你也沒救了）。讓 right-- ，繼續比較下一組數據，而 left 指針不變（因為他還是可以去匹配比 nums[right] 更小的數的）
其實和上一題差不多，相對來說比較簡單
話不多說，上代碼

class Solution 
{
public:vector<int> twoSum(vector<int>& price, int target) {int left = 0, right = price.size()-1;while(left < right){int sum = price[left] + price[right];if(sum == target)return {price[left],price[right]};else if(sum > target) right--;else left++; }return {-1,-1};}
};

兩數之和

兩數之和

思路

其實和上一題差不多的，就是初始化 left 和 right 兩個指針
然后對撞找出 numbers[left] + numbers[right] == target 的兩個數就好啦
話不多說，上代碼

class Solution 
{
public:vector<int> twoSum(vector<int>& numbers, int target) {int left = 0, right = numbers.size() - 1;while(left < right){if(numbers[left] + numbers[right] > target){right--;}else if(numbers[left] + numbers[right] < target){left++;}else{return {left + 1, right + 1};}}return {-1, -1};}
};

三數之和

三數之和

思路

本題與兩數之和類似，與兩數之和稍微不同的是，題目中要求找到所有「不重復」的三元組。
那我們可以利用在兩數之和（上一題）那里用的雙指針思想，來對我們的暴力枚舉做優化：
先排序；
然后固定一個數 a ：
在這個數后面的區間內，使用「雙指針算法」快速找到兩個數之和等于 -a 即可。但是要注意的是，這道題里面需要有**「去重」操作**~
找到一個結果之后， left 和 right 指針要「跳過重復」的元素；
當使用完一次雙指針算法之后，固定的 **a 也要「跳過重復」**的元素。
思路比較簡單，但是代碼還是有點多

class Solution
{
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;int n = nums.size();sort(nums.begin(),nums.end());for(int i = 0; i < n; ){if(nums[i] > 0) break;int left = i + 1, right = n - 1, target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum > target)right--;else if(sum < target)left++;else{ret.push_back({nums[i], nums[left], nums[right]});left++,right--;while(left < right && nums[left - 1] == nums[left]) left++;//  去重while(left < right && nums[right + 1] == nums[left]) right--; // 去重}}i++;while(i < n && nums[i] == nums[i - 1]) i++;//  去重處理}return ret;}
};

四數之和

四數之和

思路

和上題差不多的，就是加了一個數而已啦
依次固定一個數 a ；
在這個數 a 的后面區間上，利用「三數之和」找到三個數，使這三個數的和等于 target- a 即可

class Solution 
{
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {int n = nums.size();vector<vector<int>> ret;sort(nums.begin(), nums.end());for(int i = 0; i < n; ){for(int j = i + 1; j < n; ){int left = j + 1, right = n - 1;long long aim = (long long)target - nums[i] - nums[j];while(left < right){int sum = nums[left] + nums[right];if(sum < aim) left++;else if(sum > aim)right--;else{ret.push_back({nums[i], nums[j], nums[left], nums[right]});left++, right--;while(left < right && nums[left - 1] == nums[left]) left++;while(left < right && nums[right + 1] == nums[right]) right--;}}j++;while(j < n && nums[j] == nums[j - 1]) j++;}i++;while(i < n && nums[i] == nums[i - 1])i++;}return ret;}
};

總結

今天對雙指針有了新的理解，每一題的練習都是堆知識更加一步的理解
小編將持續不斷為大家更新算法題，以及算法知識
一起加油呀~~~~~