算法练习之双指针算法

本文主要是介绍算法练习之双指针算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

一、移动零【做题链接】

二、复写零【做题链接】

三、快乐数【做题链接】

四、盛水最多的容器【做题链接】

五、查找总价值为目标值的两件商品【做题链接】

六、三数之和【做题链接】

七、四数之和【做题链接】

八、有效三角形的个数【做题链接】

总结

前言

欢迎感兴趣的小伙伴交流学习。

一、移动零【做题链接】

题目代码：

class Solution {
public:void moveZeroes(vector<int>& nums) {int green_pointer = 0;int blue_pointer = -1;for (; green_pointer < nums.size(); green_pointer++){if (nums[green_pointer] != 0){blue_pointer++;int tmp;tmp = nums[green_pointer];nums[green_pointer] = nums[blue_pointer];nums[blue_pointer] = tmp;}}}
};

二、复写零【做题链接】

题目代码：

class Solution {
public:void duplicateZeros(vector<int>& arr){int write = arr.size() - 1;int count_write_zore = 0;int read;int i = 0;for (; count_write_zore < arr.size(); i++){count_write_zore++;if (arr[i] == 0){count_write_zore++;}}read = i - 1;for (; read >= 0; read--){arr[write--] = arr[read];if (arr[read] == 0 && (read != i - 1 || count_write_zore == arr.size())){arr[write--] = arr[read];}}}
};

三、快乐数【做题链接】

题目代码：

class Solution {
public:int count(int n){int ret=0;while(n%10!=0||n/10){ret+=pow(n%10,2);n/=10;}cout<<ret<<" ";return ret;}bool isHappy(int n) {int fast_pointer=count(count(n));int slow_pointer=n;while(fast_pointer!=slow_pointer){   fast_pointer=count(count(fast_pointer));cout<<"(";slow_pointer=count(slow_pointer);cout<<")";}if(fast_pointer==1){return true;}return false;}
};

四、盛水最多的容器【做题链接】

class Solution {
public:int maxArea(vector<int>& height) {int left=0;int right=height.size()-1;int ret=0;while(left<right){ret=max(ret,(right-left)*min(height[right],height[left]));if(height[left]<height[right]){left++;}else if(height[left]>=height[right]){right--;}cout<< ret<<" "<<left<<" ";}return ret;}
};

五、查找总价值为目标值的两件商品【做题链接】

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

六、三数之和【做题链接】

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

七、四数之和【做题链接】

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

八、有效三角形的个数【做题链接】

class Solution {
public:int triangleNumber(vector<int>& nums) {if (nums.size() < 3) return 0;sort(nums.begin(), nums.end());int ret = 0;int n = nums.size();for (int i = n - 1; i >= 2; --i){//固定住最长的那条边int l = 0, r = i - 1;//l,r分别代表两条边while (l < r){if (nums[l] + nums[r] > nums[i]){ret += r - l;--r;}else{++l;}}}return ret;}
};