双指针-【3，4，5，6，7，8】

第三题：快乐数

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/happy-number/算法思想：

1.每个节点的值是唯一的（因为会形成环），所以用节点的值充当指针。

2.快指针走两步，慢指针走一步，下次相遇时在环内。

3.如果是快乐数，则环中的数字全是1，否则都不是1（因为1的下一个就是1），直接判定相遇时节点的值即可。

4.一定会形成环，这里就不证明了，因为题目条件给了。（就算不给，也是一定成环的）。

代码实现：

class Solution {
public:int next(int n) {int res=0;while(n) {res+=(n%10)*(n%10);n/=10;}return res;}bool isHappy(int n) {int slow=n,fast=n;do {fast=next(fast);fast=next(fast);slow=next(slow);}while(fast!=slow);if(fast==1) return true;return false;}
};

第四题：盛水最多的容器

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/container-with-most-water/

算法思想：

V = Height* Width（Height取较小的那一个）

取两头，对于当中较短的边，这已经是最好的情况了（此时宽度取最大（区间长度），高度也取最大（自己本身）），将其计入后就不用再考虑了。现在区间缩小了。

如此循环下去，区间比1小时（l>=r）即可退出。

代码实现：

class Solution {
public:int maxArea(vector<int>& height) {int l=0,r=height.size()-1,res=0;while(l<r) {int NewRes=min(height[l],height[r])*(r-l);if(NewRes>res) res=NewRes;if(height[l]>height[r]) --r;else ++l;}return res;}
};

第五题：有效三角形之和

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/valid-triangle-number/算法思想：

1.排序，使数组单调递增。

2.固定最大的数（下标最小是2，否则凑不到三个数），然后从该数组左边的区间取剩下的两个数字。

3.取小区间的两头（一个最小(l)，一个最大(r)）

如果这两个数足够大（max太大了，min都能带动，其他的更能带的动），res+=r-l;   --r;（r已经计算完了）

如果这两个数不够大（min太小了，max都带不动），++l;（ l 太小了，没有利用价值了）

当l与r相遇时，这个大数就计算完了

4.计算下一个大数，一直循环到最后一个

代码实现：

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

第六题：两数之和

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/算法思想：

取区间的两头（一个最小(l)，一个最大(r)）

如果这两个数大了（max太大了，带上最小的数还是超过了target，所以min无用） --r;

如果这两个数小了（min太小了，带上了最大的数都够不到target，所以max无用）++l;

如果相等就找到了，走人！

每一次行动都会让区间宽度减1，如果减没了（也就是两指针相遇）还没找到，那就是没有了。

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

第七题：三数之和

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/3sum/算法思想：

排序+双指针

注意：去重

1.固定一个数，然后在他右边（因为本思路左边的数都计完了）的区间利用双指针解决两数之和问题。

运行双指针时去重：

对于l：如果加加完了，数值不变，则继续加加，一直到数值变化

对于r：如果减减完了，数值不变，则接着减减，一直到数值变化

2.固定第一个，在固定下一个，将数组遍历一遍。

遍历时去重：如果加加完了，数值不变，则继续加加，一直到数值变化

在连续加加减减时，要注意越界问题。

解决方案：在连续加加减减时，每变化一次，判定一次

代码实现：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> res;int size=nums.size();for(int i=0;i<size;) {if(nums[i]>0) break;int j=i+1,k=size-1;while(j<k) {if(nums[i] +nums[j]+nums[k]>0) --k;else if(nums[i]+nums[j]+nums[k]<0) ++j;else {res.push_back({nums[i],nums[j],nums[k]});++j; --k;while(j<k&&nums[j-1]==nums[j]) ++j;while(j<k&&nums[k]==nums[k+1]) --k;}}++i;while(i<size-2&&nums[i]==nums[i-1]) ++i;}return res;}
};

第八题：四数之和

算法思想：

排序+双指针

注意：去重

1.从左到右轮流固定每一个数，然后在他右边的区间利用双指针解决三数之和问题。

2.去重问题和三数之和类似，此处略。

代码实现：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> res;int size = nums.size();for(int i=0;i<size-3;) {for(int j=i+1;j<size-2;) {int k=j+1,r=size-1;while(k<r) {if((long)nums[i]+nums[j]+nums[k]+nums[r]<target) ++k;else if((long)nums[i]+nums[j]+nums[k]+nums[r]>target) --r;else if((long)nums[i]+nums[j]+nums[k]+nums[r]==target) {res.push_back({nums[i],nums[j],nums[k],nums[r]});++k; --r;while(k<r&&nums[k]==nums[k-1]) ++k;while(k<r&&nums[r]==nums[r+1]) --r;}}++j;while(j<size-2&&nums[j]==nums[j-1]) ++j;}++i;while(i<size-3&&nums[i]==nums[i-1]) ++i;}return res;}
};