双指针

(1)快慢双指针

适用于使用双指针进行元素移动，覆盖

(2)首尾双指针

计算区域面积，三数之和

1、移动0

（1）题目描述以及输入输出

(1)题目描述:
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
(2)输入输出描述：
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]关键思路：
fast遍历数组，slow用于指向零。遍历时，不为0元素时，slow与fast进行swap(),都会向右移动;0时，仅fast移动。

（2）代码块

class Solution {
public:void moveZeroes(vector<int>& nums) {int left = 0;int right = 0;if(nums.size() == 1)return;while(right<nums.size()){if(nums[right]){swap(nums[left],nums[right]);left++;}right++;}}
};

2、盛水最多的容器

（1）题目描述以及输入输出

(1)题目描述:
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
(2)输入输出描述：
输入：height = [1,1]
输出：1关键思路：
首尾双指针while遍历数组，计算区域面积：(right-left)*min(height[left],height[right])
接着偏移左右双指针，height[left]<height[right],left++，找高边缘。

（2）代码块

class Solution {
public:int maxArea(vector<int>& height) {int left = 0;int right = height.size()-1;int area = 0;int result = 0;while(left<right){area = (right-left)*min(height[right],height[left]);	//计算区域高度result = max(area,result);if(height[left]<height[right])							// 找下一个高边缘left++;elseright--;}return result;}
};

3、三数之和

（1）题目描述以及输入输出

(1)题目描述:
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
(2)输入输出描述：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]关键思路：
遍历数组元素，遍历到该元素时先对元素进行去重，使用首尾双指针while计算三者相加的和，再进行首尾指针移动；
找到和为0的三元素后，插入结果，并对接下来的首尾指针进行去重，去重后指针均向中间移动。

（2）代码块

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());		// 先对数组排序vector<vector<int>> result;int left,right;for(int i = 0;i<nums.size();i++){if(nums[i] > 0)return result;if(i>0 && nums[i] == nums[i-1])	// 首元素去重continue;left = i+1;right = nums.size()-1;while(left<right){if(nums[i] + nums[left] + nums[right] > 0)	// 根据相加结果平移指针right--;else if(nums[i] + nums[left] + nums[right] < 0)left++;else										// 找到三数后进行去重{result.push_back(vector<int>{nums[i],nums[left],nums[right]});while(left<right && nums[left] == nums[left+1])left++;while(left<right && nums[right] == nums[right-1])right--;left++;right--;}}         }    return result;}
};