算法沉淀一：双指针

目录

前言：

双指针介绍

对撞指针

快慢指针

题目练习

1.移动零

2.复写零

3.快乐数

4.盛水最多的容器

5.有效三角形的个数

6.和为s的两个数

7.三数之和

8.四数之和

前言：

此章节介绍一些算法，主要从leetcode上的题来讲解，讲解内容为做题思路，附加代码。

欢迎与我大家一起学习共同进步！沉淀！passion！

双指针介绍

双指针的常见形式有两种：对撞指针，快慢指针。

对撞指针

• 对撞指针也称为左右指针，一个在最左边，一个在最右边，逐渐往中间逼近。
• 对撞指针的终止条件一般是两个指针相遇或者是错开，也有可能是找到了结果直接跳出循环。

        left == right （两个指针指向同⼀个位置）

        left  >  right （两个指针错开）

快慢指针

其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用。其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。快慢指针的实现方式有很多种，最常用的⼀种就是：

• 在⼀次循环中，每次让慢的指针向后移动⼀位，而快的指针往后移动两位，实现⼀快⼀慢。

题目练习

1.移动零

leetcode题目链接

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:输入: nums = [0,1,0,3,12]  输出: [1,3,12,0,0]

示例 2:输入: nums = [0]      输出: [0]

解法（快排的思想：数组划分区间 - 数组分两块）：

算法思路：

cur 从前往后遍历的过程中:

1、遇到0                    cur++;

2、遇到非0元素          swap(dest+1,cur)      dest++，cur++; 

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int cur = 0, dest = -1; cur < nums.size(); cur++)
            if(nums[cur]) // 处理⾮零元素
                 swap(nums[++dest], nums[cur]);
    }
};

2.复写零

leetcode题目链接

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：输入：arr = [1,0,2,3,0,4,5,0] 输出：[1,0,0,2,3,0,0,4]

解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：输入：arr = [1,2,3]                输出：[1,2,3]

解释：调用函数后，输入的数组将被修改为：[1,2,3]

解法：

先根据“异地”操作，然后优化成双指针下的“就地”操作。异地就是再开辟一个数组，cur遇到非0，dest复制下来，是0的话，就复写两边。但是现在是要就地操作，cur和dest都放在同一个数组，如果从前往后，直接复写的话，复写会覆盖后面的元素。所以考虑从后往前操作。

1、先找到最后一个”复写“的数

        双指针算法   cur = 0,  dest = -1

                1.先判断cur的位置的值

                2.决定dest向后移动一步或者两步

                3.判断一下dest是否已经到结束为止

                4.cur++

                5.处理边界情况：[ 1,0,2,3,0,4]

                        n-1 == 0

                        cur--

                        dest -= 2

2、”从后向前“完成复写操作

代码：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size(), cur = 0, dest = -1;
        //找到最后一个复写元素
        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 -= 2;
        }
        //3.从后往前完成复写操作
        while (cur >= 0)
        {
            if (arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

3.快乐数

leetcode题目链接

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：输入：n = 19 输出：true

解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

示例 2：输入：n = 2 输出：false

示例1的解释，就是每位数的平方相加，最后等于1

示例2则是  2 - 4 - 16 - 37 - 58 - 89 - 145 - 42 - 20 - 4 最后会变成这些数其中的一位，跟链表中的环形链表相似，我们则可以把它抽象成环形链表相遇的问题，当相遇的时候，bool值不是1，则不是快乐数。是1，则是快乐数。

class Solution
{
public:
    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(bitSum(fast));
        }
        return slow == 1;
    }
};

4.盛水最多的容器

leetcode题目链接

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：输入：[1,8,6,2,5,4,8,3,7] 输出：49

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：输入：height = [1,1] 输出：1

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ret = 0;

        while (left < right)
        {
            int v = min(height[left], height[right])*(right - left);
            ret = max(ret, v);//记录最大容器面积
            if (height[left] < height[right]) left++;//最小的数组决定水桶的最大容积
            else right--;
        }
        return ret;
    }
};

5.有效三角形的个数

leetcode题目链接

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:输入: nums = [2,2,3,4] 输出: 3

解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3

示例 2:输入: nums = [4,2,3,4] 输出: 4

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
		int ret = 0;//记录有多少个三角形
		int n = nums.size();
		for (int i = n - 1; i >= 2; i--) {
			int left = 0;
			int right = i - 1;
			while (left < right) {
				if (nums[left] + nums[right] > nums[i]){
					ret += right - left;
                    right--;
                }
				else left++;
			}
		}
		return ret;
    }
};

6.和为s的两个数

leetcode题目链接

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例 1：输入：price = [3, 9, 12, 15], target = 18               输出：[3,15] 或者 [15,3]

示例 2：输入：price = [8, 21, 27, 34, 52, 66], target = 61 输出：[27,34] 或者 [34,27]

解法思路： 

首先肯定想的就是暴力枚举，双重循环。其实很多方法都是在暴力枚举上进行优化的。此题一样可以优化。

观察题目可知，要得出 target ，那么在两数相加(sum)时，就得有三种判断，

target > sum  ---->  sum++

target < sum  ---->  sum--

target = sum  ---->  return{left，right}

我们顺着这个思路来，既然是两数，使用双指针（对撞指针），一个在最左边，一个在最右边，如果两个指针发生了对撞，那么就证明这个数组中是没有答案的。

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int n = price.size();
        int left = 0, right = n -1;
        while(left<right){
            int sum = price[left] + price[right];
            if (sum == target){
                return {price[left],price[right]};
            }
            else if(sum > target){
                right--;
            }
            else{
                left++;
            }
        }
        return {0,0};
    }
};

7.三数之和

leetcode题目链接

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

解释：

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。

示例 2：输入：nums = [0,1,1] 输出：[]

解释：唯一可能的三元组和不为 0 。

示例 3：输入：nums = [0,0,0] 输出：[[0,0,0]]

解释：唯一可能的三元组和为 0 。

想法思路：

其实做这个题目可以在上一个题目的基础下来建立思路，这是一个三数之和相加为0，上一题是两数相加为0。那么多出来的一个数，则就可以看成是另外两个数之和的相反数。两数相加为sum，还有一个数则为-sum，如果这两个条件成立的情况下，那么就是三数之和的答案，但是还需要去重，这题难在去重。

解法步骤：

1.暴力枚举（排序+枚举+利用容器去重）（O^3)

2.优化（排序+双指针）

•         排序
•         固定一个数sum
•         利用双指针left和right在后面区间找到相加 == -sum的两个数

3.处理细节问题

        去重（利用set，但是这里利用其他方法）（考虑越界问题）

                1.left 和 right 跳过相同的元素

                2.sum也要跳过相同的元素

        不漏

               找到一种结果后不要停，继续缩小区间 

解法思路： 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;//存储三数之和等于0的三个数组，二维数组
		//排序
		sort(nums.begin(), nums.end());
		//用双指针
		int n = nums.size();
		for (int i = 0; i < n;)
		{
			if (nums[i] > 0) break;
			int left = i + 1, right = n - 1, target = -nums[i];	//确定基数target
			
			while (left < right)
			{
                int sum = nums[left] + nums[right];
				if (sum > target) right--;
                //while() 去重，再添加这一步也可以
				else if (sum < target) left++;
                //while() 去重，再添加这一步也可以
				else {
					ret.push_back({ nums[i],nums[left],nums[right] });
					left++, right--;
                    //这连个while只能写在这个if里面，因为其他两个条件分别对left/right 单独进行操作，而这里是对两个都进行了操作，如果放在外面的话，可能导致越界访问的情况。
					while (left < right && nums[left] == nums[left - 1]) left++;//去重left
					while (left < right && nums[right] == nums[right + 1])right--;//去重right
				}
			}
        //去重基数nums[i]
		i++;
		while (i < n && nums[i] == nums[i - 1]) i++;
		}
		return ret;
    }
};

8.四数之和

leetcode题目链接

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

这题的解法和三数之和的解法一样，只是多定义了一个基数而已。没有本质上的区别。 

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        int n = nums.size();
        //定第一个基数
        for (int i = 0; i < n;)
        {
            for (int j = i + 1; j < n;)//第二个基数
            {
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum > aim) right--;
                    //while() 去重
                    else if (sum < aim) left++;
                    //wihle() 去重
                    else{
                        ret.push_back({nums[i],nums[j],nums[left],nums[right]});
                        left++, right--;
                        //去重双指针，只能在sum == aim 里，这两步才能写，不然没有进来的话，if/else if都只是对left/right进行了操作，另外一个可能导致越界访问
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[ right + 1]) right--;
                    }
                }
                //去重第二个数
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            //去重第一个数
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};