个人主页：CSDN_小八哥向前冲
所属专栏：基础算法
目录
移动零
复写零
快乐数
盛最多水的容器
有效三角形的个数
和为s的两个数
三数之和
四数之和
移动零
题目：【LeetCode】移动零
思路：
这里其实就是一个数组分块的问题，将数组分块即：前一个部分非零，而后一个部分为零。
定义双指针，一个指针(cur)遍历，另一个指针(dest)分割非零和零部分。
cur指针在遍历的过程中有两种情况，一是碰到零和碰到非零，当碰到零时，dest指针不变，cur指针前进一步，碰到非零时，dest前进一步(此时dest是指向零)，再和cur指向交换，一直循环这个动作。
图：
代码：
class Solution {
public:void moveZeroes(vector<int>& nums) {int dest=-1;for(int cur=0;cur<nums.size();cur++){if(nums[cur]){swap(nums[++dest],nums[cur]);}}}
};复写零
题目：【LeetCode】复写零
思路：
利用双指针，我们可以模拟一下从前到后去修改数组，但是发现会覆盖掉原数组的数！
所以，我们可以模拟一下从后到前去修改数组，发现可行！
图：
但是有一个特殊情况：
代码：
class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur=0,dest=-1,n=arr.size();//将两指针挪到对应的位置while(cur<n){if(arr[cur]){++dest;}else{dest+=2;}if(dest>=n-1){break;}++cur;}//修正两指针的位置if(dest>=n){--cur;arr[n-1]=0;dest-=2;}//开始就地复写操作while(cur>=0){if(arr[cur]){arr[dest--]=arr[cur--];}else{arr[dest--]=0;arr[dest--]=0;--cur;}}}
};快乐数
题目：【LeetCode】快乐数
题意分析：
思路：
我们可以将它们看成有环的链表，只需判断环内的数是不是1，还是其他数字。
定义快慢指针，快指针走两步，慢指针走一步，当进环后，快指针追上慢指针，判断此时是否为1就解决了！
代码：
class Solution {
public:int Happybit(int n){int sum=0;while(n){int t=n%10;sum+=t*t;n/=10;}return sum;}bool isHappy(int n) {int slow=n,fast=Happybit(n);while(slow!=fast){slow=Happybit(slow);fast=Happybit(Happybit(fast));}return fast==1;}
};盛最多水的容器
题目：【LeetCode】盛水最多的容器
思路：
代码：
class Solution {
public:int maxArea(vector<int>& height) {int left=0,right=height.size()-1;//存较大容器的值int ret=0;while(left<right){//找出较大的值int v=min(height[left],height[right])*(right-left);ret=max(v,ret);//开始挪动if(height[left]<height[right]){left++;}else{right--;}}return ret;}
};有效三角形的个数
题目：【LeetCode】有效三角形的个数
思路：
代码：
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int n=nums.size(),sum=0;int key=n-1;//不断取最大的数while(key>=2){int left=0,right=key-1;//每趟while(left<right){if(nums[left]+nums[right]>nums[key]){sum+=right-left;right--;}else{left++;}}key--;}return sum;}
};和为s的两个数
题目：【牛客】和为s的两个数
思路：
显然，时间太长了，不符合题目要求。
三数之和
题目：【LeetCode】三数之和
思路：
代码：
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> vv;sort(nums.begin(),nums.end());int n=nums.size();for(int key=0;key<n;){//当key本身就是大于0的话，那么三数就一定不可能为0if(nums[key]>0) break;int left=key+1,right=n-1;while(left<right){int sum=nums[left]+nums[right];int targrt=-nums[key];if(sum<targrt) left++;else if(sum>targrt) right--;else{vv.push_back({nums[key],nums[left],nums[right]});left++;right--;//去除重复数据,小心越界while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}//去重keykey++;while(key<n&&nums[key]==nums[key-1]) key++;}return vv;}
};四数之和
题目：【LeetCode】四数之和
思路：
代码：
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> vv;int n=nums.size();for(int key1=0;key1<n;){for(int key2=key1+1;key2<n;){int left=key2+1,right=n-1;while(left<right){int sum=nums[left]+nums[right];long long tmp=(long long)target-nums[key1]-nums[key2];if(sum<tmp) left++;else if(sum>tmp) right--;else{vv.push_back({nums[key1],nums[key2],nums[left],nums[right]});left++;right--;//将数据去重，注意越界情况while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}//将key2去重key2++;while(key2<n&&nums[key2]==nums[key2-1]) key2++;}//将key1去重key1++;while(key1<n&&nums[key1]==nums[key1-1]) key1++;}return vv;}
};这些就是双指针类型常见题目，我们下期见！
