优选算法第一讲：双指针模块

1.移动零
2.复写零
3.快乐数
4.盛最多水的容器
5.有效三角形的个数
6.查找总价格为目标值的两个商品
7.三数之和
8.四数之和

1.移动零

链接: 移动零
下面是一个画图，其中，绿色部分标出的是重点：
在这里插入图片描述
代码实现：

class Solution {
public:void moveZeroes(vector<int>& nums) {//定义双指针for(int cur = 0, des = -1; cur < nums.size(); cur++){//当cur指向的位置不为0时，才进行交换if(nums[cur]){swap(nums[cur], nums[++des]);//注意：先++des，再进行交换}}}
};

2.复写零

链接: 复写零
在这里插入图片描述
代码实现：

class Solution {
public:void duplicateZeros(vector<int>& arr) {//先找到src的位置int src = 0, des = -1, n = arr.size();while(src < n){if(arr[src]) des++;else des+=2;if(des >= n-1) break;src++;}if(des == n){//发生了越界时，修正des的位置arr[n-1] = 0;src--;des -= 2;}//从后向前复写while(des > 0){if(arr[src])arr[des--] = arr[src--];else{arr[des--] = 0;arr[des--] = 0;src--;}}}
};

3.快乐数

链接: 快乐数
在这里插入图片描述

class Solution {
public://按照题意求值int Value(int n){//循环*10 %10，C语言中讲过int sum = 0;while(n){int t = n % 10;sum += t*t;n = n /10;}return sum;}bool isHappy(int n) {int slow = n, fast = Value(n);while(slow != fast){slow = Value(slow);fast = Value(Value(fast));}return slow == 1;}
};

4.盛最多水的容器

链接: 盛最多水的容器
在这里插入图片描述
代码实现：

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

5.有效三角形的个数

链接: 有效三角形的个数
在这里插入图片描述

class Solution {
public:int triangleNumber(vector<int>& nums) {//1.先对数组进行排序sort(nums.begin(), nums.end());int sum = 0;for(int i = nums.size()-1; i>=2; i--){//i为最大值的下标//使用双指针进行运算int left = 0, right = i-1;while(left < right){if(nums[left] + nums[right] > nums[i]){sum += right-left;right--;}else left++;}}return sum;}
};

6.查找总价格为目标值的两个商品

链接: 查找总价格为目标值的两个商品
在这里插入图片描述

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {//因为题目说明已经是升序了，所以我们不用再进行排序了//使用双指针算法int left = 0, right = price.size()-1;while(left < right){if(price[left] + price[right] > target) right--;else if(price[left] + price[right] < target) left++;else return {price[left], price[right]};}return {0, 0};}
};

7.三数之和

在这里插入图片描述

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;//1.先对数组进行排序sort(nums.begin(), nums.end());//对i的固定int i = 0;while(i <= nums.size()-3){//双指针算法int left = i+1, right = nums.size()-1;while(left < right){if(nums[left] + nums[right] > -nums[i]) right--;else if(nums[left] + nums[right] < -nums[i]) left++;else{//当相等时，先插入数据ret.push_back(vector<int>({nums[left], nums[right], nums[i]}));//再处理去重问题left++;right--;while(left < right && nums[left] == nums[left-1]) left++;while(left < right && nums[right] == nums[right+1]) right--;}}//对i进行去重i++;while(i <= nums.size()-3 && nums[i] == nums[i-1]) i++;}return ret;}
};