目录
题目1：移动零
题目2：复写零
题目3：快乐数
题目4：最多水的容器
题目5：有效三角形的个数
题目6：两数之和为s
题目1：移动零
给定一个数组nums，编写一个函数将所有的0移动到数组的末尾同时保持非0元素的相对顺序。(就地实现)
示例
散乱数组：nums{0，1，0，3，12 }==》nums{1,3，12，0，0}
算法原理：利用双指针（数组下标充当指钱）来实现数组划分
如果cur处为非0，交换dest+1和cur处的值同时两个下标向右走，开始处理dest=-1；cur=0;
实现代码：
void moveZeroes(vector<int>& nums)
{for (int cur = 0, dest = -1; cur < nums.size(); cur++){if (nums[cur]){swap(nums[++dest], nums[cur]);}}
}
题目2：复写零
给定一个长度固定的整数数组arr，将该数组中出现的每个0都复写一遍，将其余元素向右平移，不开辟新空间，就地复写
示例：
{1，0，2，3，0，4，5，0}==》{1，0，0，2，3，0，0，4}
算法原理：
1.先找到最后一个复写的数
从左往右遍历cur指向第0个元素.
dest指向一1，若arr[cur]不为0，dest和cur都向后走一步若：arr[cur]为0，则dest何右走两走两步，cur向右走一步。
2.调整边界
3.从右往左完成复写
实现代码：
void doubleZeroes(vector<int>& arr)
{//1.先找到最后一个复写的数int cur = 0, dest = -1, n = arr.size();while (cur < n){if (arr[cur])dest++;else dest += 2;if (dest >= n - 1)break;cur++;}//2.处理边界if (dest == n){arr[n - 1] = 0;cur--; dest--;}//3.从右往右完成复写while (cur >= 0){if (arr[cur])arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}
}//3.快乐数题目3：快乐数
编写一个算法来判断一个数是不是快乐数。
快乐数定义为：
1.对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,也可能是无限循环但始给达不到1如果这个过程结果为1,那么这个数就是快乐数，如果n是快乐数就返回true，不是则返回false。
1、题目解析
示例：n=19 n=2
9²+9²=82 2²=4
8²+2²=68 4²=16
6²+8²=100 1²+6²=37
1²+0²+0²=1 3²+7²=58......89->145->42->20...2²+0²=2
19就是快乐数 ，2不是快乐数。
解法：快慢指针
定义：
1.定义快慢指针
2.慢指针每一次向后移动一步
3.快指针每一次向后移动两步
根据鸽巢原理快慢指针最终会相遇
4.判断相遇的值即可
代码实现：
int bitSum(int n)//返回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 = bitSum(n);while (slow != fast){slow = bitSum(slow);fast = bitSum(fast);}return fast == 1;
}
题目4：最多水的容器
给定一个长度为n的整数数组height，有n条垂线，第i条钱的两个端点是(i,0)和(i,height[i])。找出其中两条线，使得它们与X轴共同构成的容器可以容纳最多的水，返回容器可以储存的最大水量。
算法思想：
代码实现：
int maxArea(vector<int>& height)
{int left = 0, right = height.size() - 1, ret = 0;while (left < right){int v = min(height[right], height[left]) * (right - left);ret = max(ret, v);if (height[right] > height[left])left++;else right--;}return ret;}题目5：有效三角形的个数
给定一个包含非负整数的数组nums，返回其中可以组成三角形三条边的三元组个数。
示例：如nums={2，2，3，4}
输出3。
解法—：暴力校举
解法二：利用单调性使用双指针算法。
1.对数组排序
2.当对数组进行排序后，我们选定最右边的元素作为第三边，此时，只需在其的左区间找到两个元素之和大于它两组成三角形（最小两边之和大于最大的一边）
以{2，2，3，4，5，8，9，10}为例
nums[left]为左区间的最小值，而nums[right]为左区间的最大值，若此时nums[left]与nums[right]之和小于10，则此时在数组 nums中nums[left]无法与10组成三角形;若此时nums[left]与nums[right]之和大于10，则nums[right]与其左区间内的任一元素，都可以和10构成三角形。
实现思想：
实现代码：
int triangNumber(vector<int>& nums)
{//1.优化sort(nums.begin(), nums.end());//2.利用双指针结合单调性快速统计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 = ret + (right - left);right--;}else{left++;}}}return ret;
}题目6：两数之和为s
输入一个递增的排序数组和一个数字S，在数组中查找两个数使得它们的和正好是S，如果有多对的数字和为S，则输出任意一对即可。
解法：利用数组递增,使用双推针解决问题
1.sum>s;right--;
2.sum<s;left++ ;
3.sum==t;return{nums[right],retunrn[left]};
代码实现：
vector<int> towSum(vector<int>& nums, int s)
{//1, 0, 2, 3, 0, 4, 5, 0int left = 0, right = nums.size()-1;while (left < right){int sum = nums[left] + nums[right];if (sum > s)right--;else if (sum < s)left++;else return { nums[left],nums[right] };}return { -1,-1 };
}
