LeetCode分类刷题：双指针(Two Pointers)
LeetCode分类刷题：双指针(Two Pointers)
本文整理自csdn
双指针(Two Pointers)一直是程序员面试中的一个必须准备的主题， 面试中双指针出现的次数比较多，主要由于在工作中指针经常用到，指针问题能够直接反应面试者的基础知识、代码能力和思维逻辑，因此双指针的问题必须掌握。
解决双指针问题三种常用思想：
左右指针：需要两个指针，一个指向开头，一个指向末尾，然后向中间遍历，直到满足条件或者两个指针相遇
快慢指针：需要两个指针，开始都指向开头，根据条件不同，快指针走得快，慢指针走的慢，直到满足条件或者快指针走到结尾
后序指针：常规指针操作是从前向后便利，对于合并和替换类型题，防止之前的数据被覆盖，双指针需从后向前便利
记忆口诀：左右指针中间夹，快慢指针走到头，后序指针往回走
LeetCode中关于双指针的题目有以下三种类型题：
(一)双指针之左右指针相关题目：
(二)双指针之快慢指针相关题目：
(三)双指针之后序指针相关题目：
(一)双指针之左右指针相关题目：
167. Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
题目要求：给定一个升序排列的整数数组，找到两个数，使它们的和等于给定的数，有且仅有一个满足条件的解，返回索引。
题目分析：需要两个指针，一个指向开头，一个指向末尾，然后向中间遍历，如果指向的两个数相加正好等于target的话，直接返回两个指针的位置即可，若小于target，左指针右移一位，若大于target，右指针左移一位，以此类推直至两个指针相遇停止。
题目解答：
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> res(2, -1);
int left = 0, right = numbers.size() - 1;
while(left < right){
int temp = numbers[left] + numbers[right];
if(temp > target){
right--;
}else if(temp < target){
left++;
}else{
res[0] = left + 1;
res[1] = right + 1;
return res;
}
}
return res;
}
};15. 3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note:The solution set must not contain duplicate triplets.
题目要求：给定n个整数的数组nums，nums中是否有元素a，b，c，满足a + b + c = 0？ 找到数组中所有的三元组。注意：解决方案中不得包含重复的三元组。
题目分析：尝试把三数和问题转化为两数和问题：同样先对数组排序，设置三个指针i,left,right，i指针指向第一个数x，则left,right要指向数组中剩余数中的两个，并且指向的两数和为-x，从而转化为两数和问题。
题目解答：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
int n = nums.size();
if(n <= 2) return res;
sort(nums.begin(), nums.end());
for(int i = 0; i < n-2; i++){
int left = i + 1, right = n - 1;
while(left < right){
int temp = nums[left] + nums[right];
if(temp > -nums[i]){
right--;
}else if(temp < -nums[i]){
left++;
}else{
vector<int> tmp{nums[i], nums[left], nums[right]};
res.push_back(tmp);
left++;
right--;
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
}
return res;
}
};16. 3Sum Closest
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
题目要求：这道题让我们求最接近给定值的三数之和。
题目分析：在上一道的15. 3Sum基础上又增加了些许难度，那么这道题让我们返回这个最接近于给定值的值，即我们要保证当前三数和跟给定值之间的差的绝对值最小，所以我们需要定义一个变量small用来记录差的绝对值。
题目解答：
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size(), res = INT_MIN, small = INT_MAX;
sort(nums.begin(), nums.end());
for(int i = 0; i < n-2; i++){
int left = i + 1, right = n - 1;
while(left < right){
int temp = nums[left] + nums[right] + nums[i];
if(abs(temp - target) < small){
res = temp;
small = abs(temp - target);
}
if(temp > target){
right--;
}else if(temp < target){
left++;
}else{
return target;
}
}
while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
}
return res;
}
};18. 4Sum
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
题目要求：给定n个整数的数组nums，nums中是否有元素a，b，c，d 满足a + b + c + d= target？ 找到数组中所有的四元组。注意：解决方案中不得包含重复的四元组。
题目分析：在上一道的15. 3Sum基础上又增加了些许难度，尝试把四数和问题转化为两数和问题：同样先对数组排序，设置四个指针k,i,left,right，k指针指向第一个数，i指针指向第二个数,则left,right要指向数组中剩余数中的两个，从而转化为两数和问题。
题目解答：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
int n = nums.size();
if(n <= 3) return res;
sort(nums.begin(), nums.end());
for(int k = 0; k < n-3; k++){
for(int i = k + 1; i < n-2; i++){
int left = i + 1, right = n - 1;
int ret = target - nums[k] - nums[i];
while(left < right){
int temp = nums[left] + nums[right];
if(temp > ret){
right--;
}else if(temp < ret){
left++;
}else{
vector<int> tmp{nums[k], nums[i], nums[left], nums[right]};
res.push_back(tmp);
left++;
right--;
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
}
while(k + 1 < n -3 && nums[k] == nums[k + 1]) k++;
}
return res;
}
};11. Container With Most Water
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
题目要求：给定n个非负整数a1, a2, ..., an, 每个都代表坐标轴上的高，其坐标为（i,ai）。可以根据这条数组构建一幅柱形图，每任意两条柱子形成一个水桶，要求找到能盛最多水的水桶的面积。
题目分析：两条垂直的线和X轴组成一个容器，灌水多少不仅与两个柱子的高度有关，也与两个柱子的距离有关，公式：S(i,j) = min(ai, aj) * (j-i)，容器不能倾斜，求容纳最多水的两个线组合。定义left和right两个指针分别指向数组的左右两端，然后两个指针向中间搜索，每移动一次算一个值和结果比较取较大的，容器装水量的算法是找出左右两个边缘中较小的那个乘以两边缘的距离
题目解答：
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int res = 0;
while(left < right){
int temp = min(height[right], height[left]);
res = max(res, temp*(right - left));
if(height[right] < height[left]) right--;
else left++;
}
return res;
}
};42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
题目要求：给定一个数组，每个元素表示海报高度，每个元素宽度均为 1 ，求这个数组能装多少雨水。
题目分析：看一种只需要遍历一次即可的解法，这个算法需要left和right两个指针分别指向数组的首尾位置，从两边向中间扫描，在当前两指针确定的范围内，先比较两头找出较小值，如果较小值是left指向的值，则从左向右扫描，如果较小值是right指向的值，则从右向左扫描，若遇到的值比当较小值小，则将差值存入结果，如遇到的值大，则重新确定新的窗口范围，以此类推直至left和right指针重合。
题目解答：
class Solution {
public:
int trap(vector<int>& height) {
int res = 0, left = 0, right = height.size() - 1;
int maxleft = 0, maxright = 0;
while(left < right){
if(height[left] < height[right]){
if(height[left] > maxleft){
maxleft = height[left];
}else{
res += maxleft - height[left];
}
left++;
}else{
if(height[right] > maxright){
maxright = height[right];
}else{
res += maxright - height[right];
}
right--;
}
}
return res;
}
};(二)双指针之快慢指针相关题目：
27. Remove Element
Given an array nums and a value val, remove all instances of that value in-place and return the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
题目要求：这道题让我们移除一个数组中和给定值相同的数字，并返回新的数组的长度。
题目分析：使用slow和fast两个指针，从头部开始遍历，遍历一次fast指针前进一步，当遍历元素不满足指定的值，slow指针前进一步，这样不满足条件的整数都被移动到数组的前面。
题目解答：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0, fast = 0, n = nums.size();
while(fast < n){
if(nums[fast] != val) nums[slow++] = nums[fast];
fast++;
}
return slow;
}
};283. Move Zeroes
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
题目要求：这道题让我们将一个给定数组中所有的0都移到后面，把非零数前移，要求不能改变非零数的相对应的位置关系，而且不能拷贝额外的数组。
题目分析：使用slow和fast两个指针，从头部开始遍历，遍历一次fast指针前进一步，当遍历元素不等于0，slow指针前进一步，这样不等于0的整数都被移动到数组的前面。
题目解答：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0, fast = 0, n = nums.size();
while(fast < n){
if(nums[fast] != 0) swap(nums[slow++], nums[fast]);
fast++;
}
}
};26. Remove Duplicates from Sorted Array
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
题目要求：这道题要我们从有序数组中去除重复项。
题目分析：这道题的解题思路是，我们使用快慢指针来记录遍历的坐标，最开始时两个指针都指向第2个数字，如果快指针指向的数等于慢指针的前1个数，则快指针向前走一步，如果不同，则两个指针都向前走一步，这样当快指针走完整个数组后，慢指针当前的坐标就是数组中不同数字的个数。
题目解答：
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 1, fast = 1, n = nums.size();
if(n <= 1) return n;
while(fast < n){
if(nums[fast] != nums[slow - 1]) nums[slow++] = nums[fast];
fast++;
}
return slow;
}
};80. Remove Duplicates from Sorted Array II
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
题目要求：这道题要我们从有序数组中去除重复项，每个数最多重复出现2次。
题目分析：与上一道解题思路相似，我们使用快慢指针来记录遍历的坐标，最开始时两个指针都指向第3个数字，如果快指针指向的数等于慢指针的前2个数，则快指针向前走一步，如果不同，则两个指针都向前走一步，这样当快指针走完整个数组后，慢指针当前的坐标就是数组中不同数字的个数。
题目解答：
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 2, fast = 2, n = nums.size();
if(n <= 2) return n;
while(fast < n){
if(nums[fast] != nums[slow - 2]) nums[slow++] = nums[fast];
fast++;
}
return slow;
}
};287. Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n(inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
题目要求：在一个长度为n+1的数组中，每个数都是1-n之间，只有一个数出现两次，其他的数都只出现过一次，请找出这个数。
题目分析：核心思想快慢指针，由于题目限定了区间[1,n]，所以可以巧妙的利用坐标和数值之间相互转换，而由于重复数字的存在，那么一定会形成环，我们用快慢指针可以找到环并确定环的起始位置，确实是太巧妙了！
题目解答：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = nums[0], fast = nums[nums[0]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while(slow != fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};(三)双指针之后序指针相关题目：
88. Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
题目要求：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1中，使得 num1 成为一个有序数组。你可以假设 nums1有足够的空间（空间大小大于或等于m + n）来保存 nums2 中的元素。在 nums1 和 nums2 中初始化的元素的数量分别是 m 和 n。
题目分析：算法思想是：由于合并后A数组的大小必定是m+n，所以从最后面开始往前赋值，先比较A和B中最后一个元素的大小，把较大的那个插入到m+n-1的位置上，再依次向前推。如果A中所有的元素都比B小，那么前m个还是A原来的内容，没有改变。如果A中的数组比B大的，当A循环完了，B中还有元素没加入A，直接用个循环把B中所有的元素覆盖到A剩下的位置。
题目解答：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n -1;
while(i >= 0 && j >= 0){
if(nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
while(j >= 0) nums1[k--] = nums2[j--];
}
};