目录
一、快乐数：
二、有效三角形的个数：
三、盛最多水的容器：
四、复写0：
五、三数之和：
总结：
一、快乐数：
题目出处：
202. 快乐数 - 力扣（LeetCode）
https://leetcode.cn/problems/happy-number/
题目说明：
输入示例：
如上图所示：
当输入一个数字的时候，经过多次变化，一定会进入一个圆，如果最后是1可以看做一个圆，里面都是1。如果不是1，那么一定会进入一个圆里面。那么会不会出现一个无限不循环的呢？答案是不会的。
证明思路：
首先，正整型最大的是2147483647，那么便于计算将9999999999代替它，那么将9999999999经过题目所给的方式计算后的结果为810，所以经过题目的操作后，其结果肯定在0~810中，所以一个数字经过811次题目所给操作后肯定会有重复的，那么就会进入一个圆
解题思路：
首先定义快慢指针，慢指针指向输入的数，快指针指向进行一次题目操作后的数字，
因为要多次进行题目所给的操作，所以就需要将题目所给操作封装成一个函数，
最后使用循环判断知直到二者相遇就结束循环，最后返回二者之一是否等于1即可
class Solution {
public:
int func(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 = func(n);
while(slow != fast)
{
slow = func(slow);
fast = func(func(fast));
}
return slow == 1;
}
};二、有效三角形的个数：
题目出处：
611. 有效三角形的个数 - 力扣（LeetCode）https://leetcode.cn/problems/valid-triangle-number/题目说明：
输入示例：
解题思路：
既然可以包含重复的，那么就不需要进行去重操作。
主要思路是暴力解法（将每一个情况都列举出来，之后通过三角形两边之和大于另一边进行判断），双指针在暴力解法上更加快速：（三角形最短两边之和大于最长的一边）
那么就将整个数组进行排序（因为这样的话就方便使用双指针进行操作）
需要三个变量，一个指向最左边作为短边，一个指向最右边作为最长的一边，另一个在中间的区间进行寻找能够构成三角形的三个数字。
其中两个if判断
一个if
如果最左边left和最右边right所在的值相加比第三边都长的话就证明左边的所有和right相加都比第三边大，这个时候直接进行right-left找到所有情况加到ret返回值即可，
另一个if就是左边最小的值和右边最大的值相加都小于等于最大的max，这样的话就证明left和右边所有相加都不能够构成三角形，left继续++即可
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
int ret = 0;
int left = 0,right = nums.size()-2,max = nums.size()-1;
while(max>left)
{
while(left < right)
{
if(nums[left]+nums[right] > nums[max])
{
ret += right-left;
right--;
}
else//nums[left]+nums[right] <= nums[max]
{
left++;
}
}
max--;
left = 0;
right = max-1;
}
return ret;
}
};三、盛最多水的容器：
题目出处：
11. 盛最多水的容器 - 力扣（LeetCode）https://leetcode.cn/problems/container-with-most-water/题目说明：
示例：
解题思路：
首先依然是双指针就定义left和right指针指向最左和最右，这里还需要宽度（right-left），高度（left和right所对应的值中小的那一个）最大体积，当前体积（如果比最大体积大就更新最大体积）
之后在循环中使用双指针，
if语句中
如果此时left所在的高度比right所在的高度小，那么就证明left~right中间的所有和此时的left组合成的容器所盛水的体积都比此时要小
所以就将left++;
如果此时left所在的高度比right所在的高度大，那么就证明left~right中间的所有和此时的right组合成的容器所盛水的体积都比此时要小
所以就将right--;
最后更新宽度，高度，此时体积和max体积比较。
循环结束后返回max体积即可
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int wide = right - left;
int high = height[left] < height[right] ? height[left] : height[right];
int tempval = 0;
int maxval = wide*high;
while(left < right)
{
if(height[left]<height[right])
{
left++;
}
else
{
right--;
}
wide--;
high = height[left] < height[right] ? height[left] : height[right];
tempval = wide*high;
if(tempval > maxval)
{
maxval = tempval;
}
}
return maxval;
}
};四、复写0：
题目出处：
1089. 复写零 - 力扣（LeetCode）https://leetcode.cn/problems/duplicate-zeros/题目说明：
解题思路：
首先对于arr数组，复写0，如果从前往后进行复写的时候会发现无论怎样都会覆盖某些值，这样就会丢失数据，那么就需要从后往前进行复写操作。
那么既然是复写，并且数组元素确定，那么肯定这个数组中存在一个数（这个数可能是中间的某个，也可能是最后一个），在进行复写操作后就变为新数组的最后一个数，那么就需要在复写之前找到这个数。
找到这个数之后就可以进行复写了。
找这个数的思路：
首先依然是定义两个“指针”，一个在数组0位置，另一个在数组-1位置（但是这个位置不会访问，也不能访问）接着往后进行遍历，一般情况下cur在dest的下一个，但是如果cur的位置不是0的话，两个都++，如果cur位置是0的话，就将dest向右移动两位，如果dest到最后的时候，此时cur位置就是要找的这个值。
但是有一个例外情况，就是dest最后+2后越界访问了，这样的话就在确定cur后进行边界检查
最后复写即可：
如果cur位置不是0就直接和dest交换，之后将二者向左移一个位置
如果cur位置是0就将cur和dest交换，之后将二者向左移一个位置，在将此时的dest修改为0，在将dest向左移一个位置。
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0;
int dest = -1;
int n = arr.size();
while(dest < n - 1)
{
//如果cur位置是0，dest就走两步，不是0就走一步
if(arr[cur])
{
dest++;
}
else
{
dest += 2;
}
if(dest >= n - 1)
break;
cur++;
}
if(dest == n)
{
arr[n-1] = 0;
cur--;
dest-=2;
}
while(cur>=0)
{
if(arr[cur])
{
swap(arr[cur--],arr[dest--]);
}
else
{
swap(arr[cur--],arr[dest--]);
arr[dest--] = 0;
}
}
}
};五、三数之和：
题目出处：
15. 三数之和 - 力扣（LeetCode）https://leetcode.cn/problems/3sum/description/题目说明：
解题思路：
思路一：
首先进行排序，在进行暴力枚举，最后再利用容器去重
上述方法由于是暴力枚举，在本题中会超时
思路二（“双指针”法）：
1、首先依然是进行排序，
2、然后分析题目，要找到三个数相加为0，其实也可以看做两个数的和等于第三个数的相反数。
3、那么就可以首先固定一个数为目标数记为ret，在这个数的后面寻找其余两个数，这两个数的和是-ret即可
注意细节：
1、题目说不能有重复的三元组，那么就需要去重操作。
去重思路：
a、容器去重，直接利用set或者unordered_set进行去重处理
b、每次找到一种结果之后将left和right指针跳过重复元素，当使用完一次双指针之后，也就是在一个ret找完后，ret也要跳过重复元素。
2、要保证不能漏。
不漏比较好处理，只需要在每次找到一种结果之后，继续走完当前情况
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> v;
int i = 0,n = nums.size();
int ret = 0;
while(i<n)
{
ret = nums[i];
int left = i+1,right = n-1;
while(left < right)
{
int sum = -(nums[left] + nums[right]);
//-4 -3 -2 -1 0 1 2 3 4 5 6 7 8
if(ret < sum) ++left;
else if(ret > sum) --right;
else
{
v.push_back({nums[i],nums[left],nums[right]});
left++;
right--;
while(left<right && nums[left] == nums[left-1]) ++left;
while(left<right && nums[right] == nums[right+1]) --right;
}
}
i++;
while(i<n && nums[i] == nums[i-1]) i++;
}
return v;
}
};总结：
双指针算法适用于一串有序的数字，能够将暴力枚举的时间复杂度降低一维，n^3->n^2
