【算法专题】双指针

这篇具有很好参考价值的文章主要介绍了【算法专题】双指针。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

双指针

常见的双指针有两种形式,⼀种是对撞指针,⼀种是左右指针。

  1. 对撞指针:⼀般用于顺序结构中,也称左右指针。
  • 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。
  • 对撞指针的终止条件⼀般是两个指针相遇或者错开(也可能在循环内部找到结果直接跳出循环),也就是:
    left == right (两个指针指向同⼀个位置)
    left > right (两个指针错开)
  1. 快慢指针:其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用。

其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,均可考虑使⽤快慢指针的思想。快慢指针的实现方式有很多种,最常用的⼀种就是:

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

下面我们看练习题目:

1. 移动零

题目链接 -> Leetcode -283.移动零

Leetcode -283.移动零

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

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

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

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

提示 :

  • 1 <= nums.length <= 10^4
  • 2^31 <= nums[i] <= 2^31 - 1

其思路的本质是快排的思想:数组划分区间 - 数组分两块;我们可以用⼀个 cur 指针来扫描整个数组,另⼀个 dest 指针用来记录非零数序列的最后⼀个位置。根据 cur 在扫描的过程中,遇到的不同情况,分类处理,实现数组的划分。在 cur 遍历期间,使 [0, dest] 的元素全部都是非零元素, [dest + 1, cur - 1] 的元素全是零。 代码如下:

		class Solution {
		public:
		    // 双指针
		    void moveZeroes(vector<int>& nums)
		    {
		        // dest 是最后一个非零元素的下标
		        int cur = 0, dest = -1;
		        while (cur < nums.size())
		        {
		            // nums[cur] 不为零先++dest,再交换两个值 
		            if (nums[cur])
		            {
		                swap(nums[++dest], nums[cur]);
		            }
		            cur++;
		        }
		    }
		};

2. 复写零

题目链接 -> Leetcode -1089.复写零

Leetcode -1089.复写零

题目:给你一个长度固定的整数数组 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]

提示:
1 <= arr.length <= 10^4
0 <= arr[i] <= 9

思路:如果从前向后进行原地复写操作的话,由于 0 的出现会复写两次,导致没有复写的数被覆盖掉。因此我们选择「从后往前」的复写策略。但是从后向前复写的时候,我们需要找到最后⼀个复写的数,因此我们的大体流程分两步:
i. 先找到最后⼀个复写的数;
ii. 然后从后向前进行复写操作

代码如下:

		class Solution {
		public:
		    void duplicateZeros(vector<int>& arr)
		    {
		        // 先用 dest 指针模拟一遍复写,当 dest == n - 1,dest 最终的位置就是复写零后数组的最终形式,可以用 cur 位置的元素覆盖它
		        int cur = 0, dest = -1, n = arr.size();
		        while (cur < n)
		        {
		            if (arr[cur] == 0) dest += 2;
		            else dest++;
		
		            if (dest >= n - 1) break;
		
		            cur++;
		        }
		        // 当 dest > n - 1 最后dest肯定走了两步,即最后复写的元素一定是零,所以直接将最后一个元素改成0后,dest向前走两步,cur向前走一步
		        if (dest == n)
		        {
		            arr[n - 1] = 0;
		            cur--, dest -= 2;
		        }
		
		        // 正常的覆盖
		        while (cur >= 0)
		        {
		            if (arr[cur] == 0)
		            {
		                arr[dest--] = 0;
		                arr[dest--] = 0;
		                cur--;
		            }
		            else
		            {
		                arr[dest--] = arr[cur--];
		            }
		        }
		    }
		};

3. 快乐数

题目链接 -> Leetcode -202.快乐数

Leetcode -202.快乐数

题目:编写一个算法来判断一个数 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 <= n <= 2^31 - 1

思路:为了方便叙述,将「对于⼀个正整数,每⼀次将该数替换为它每个位置上的数字的平方和」这⼀个操作记为 x 操作;
题目告诉我们,当我们不断重复 x 操作的时候,计算⼀定会「死循环」,死循环的方式有两种:
▪ 情况⼀:⼀直在 1 中死循环,即 1 -> 1 -> 1 -> 1…
▪ 情况⼆:在历史的数据中死循环,但始终变不到 1
由于上述两种情况只会出现⼀种,因此,只要我们能确定循环是在「情况⼀」中进行,还是在「情况⼆」中进行,就能得到结果。

代码如下:

		class Solution {
		public:
		
		    // 计算每个位上的平方相加,即进行快乐数的计算
		    int bitNum(int n)
		    {
		        int sum = 0;
		        while (n > 0)
		        {
		            int x = n % 10;
		            sum += x * x;
		            n /= 10;
		        }
		        return sum;
		    }
		
		    bool isHappy(int n)
		    {
		        // 定义快慢指针,慢指针一定可以追上快指针,最后只需判断他们相遇时的结果是否是1即可
		        int slow = n, fast = bitNum(n);
		        while (slow != fast)
		        {
		            slow = bitNum(slow);
		            fast = bitNum(bitNum(fast));
		        }
		        if (slow == 1) return true;
		
		        return false;
		    }
		};

4. 盛水最多的容器

题目链接 -> Leetcode -11.盛最多水的容器

Leetcode -11.盛最多水的容器

题目:给定一个长度为 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

提示:
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

思路:对撞指针,两个指针分别定义在数组的头和尾,假设是 left 和 right,并假设 left < right;此时 left 决定了盛水的容量,此时如果我们舍去 left 并使 left++,有可能下一条边比 left 更长,此时的盛水容量有可能变大;但是如果我们舍去 right,并使 right–,就算下一条边更长,left 还是决定了盛水的容量,所以盛水的容量不变或者减小;所以我们不能舍去长的那一条边,我们可以大胆舍去短的那一边;当我们不断重复上述过程,每次都可以舍去大量不必要的枚举过程,直到 left 与 right 相遇。期间产生的所有的容积里面的最⼤值,就是最终答案。

代码如下:

		class Solution {
		public:
		    int maxArea(vector<int>& height)
		    {
		        int n = height.size(), ret = 0;
		
		        // 定义双指针
		        int left = 0, right = n - 1;
		        while (left < right)
		        {
		            // 盛水是要看最短的那边,所以相乘用最短的板
		            ret = max(ret, (min(height[left], height[right]) * (right - left)));
		            
		            // 如果左边短了,左指针往右移;否则右指针往左移
		            if (height[left] < height[right]) left++;
		            else right--;
		        }
		        return ret;
		    }
		};

5. 有效三角形的个数

题目链接 -> Leetcode -611.有效三角形的个数

Leetcode -611.有效三角形的个数

题目:给定一个包含非负整数的数组 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

提示 :
1 <= nums.length <= 1000
0 <= nums[i] <= 1000

思路是对数组先排序,每次固定一个数,再使用对撞指针优化;具体的思路参考代码中的注释:

		class Solution {
		public:
		    int triangleNumber(vector<int>& nums)
		    {
		        // 先进行排序
		        sort(nums.begin(), nums.end());
		
		        int ans = 0;
		
		        // 先固定一个数
		        for (int i = nums.size() - 1; i >= 2; i--)
		        {
		            // 再使用双指针枚举另外两个数
		            // 其中left在从小的开始枚举,right从大的开始枚举
		            int left = 0, right = i - 1;
		            while (left < right)
		            {
		                // 如果 nums[left] + nums[right] > nums[i] 说明left到right区间都能和i构成三角形;所以ans累加上区间内的个数
		                // 累加完后left没必要++了,因为数组是有序的,left都能组成三角形,比left大的肯定可以,所以此时让 right--
		                if (nums[left] + nums[right] > nums[i])
		                {
		                    ans += (right - left);
		                    right--;
		                }
		
		                // 否则 left++
		                else
		                {
		                    left++;
		                }
		            }
		        }
		        return ans;
		    }
		};

6. 和为s的两个数字

题目链接 -> Leetcode -剑指 Offer 57.和为s的两个数字

Leetcode -剑指 Offer 57.和为s的两个数字

题目:输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

示例 1:
输入:nums = [2, 7, 11, 15], target = 9
输出:[2, 7] 或者[7, 2]

示例 2:
输入:nums = [10, 26, 30, 31, 47, 60], target = 40
输出:[10, 30] 或者[30, 10]

限制:
1 <= nums.length <= 10 ^ 5
1 <= nums[i] <= 10 ^ 6

这道题的思路与上题类似,所以直接给出代码:

		class Solution {
		public:
		    vector<int> twoSum(vector<int>& nums, int target)
		    {
		        // 因为数组已经有序,利用有序使用双指针枚举
		        int left = 0, right = nums.size() - 1;
		        while (left < right)
		        {
		            if (nums[left] + nums[right] == target) return { nums[left],nums[right] };
		
		            else if (nums[left] + nums[right] > target) right--;
		
		            else left++;
		        }
		
		        return { -1,-1 };
		    }
		};

7. 三数之和

题目链接 -> Leetcode -15.三数之和

Leetcode -15.三数之和

题目:给你一个整数数组 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 。

提示:

  • 3 <= nums.length <= 3000
  • 10^5 <= nums[i] <= 10^5

此题与两数之和类似,与两数之和稍微不同的是,题目中要求找到所有不重复的三元组。那我们可以利用在两数之和那里用的双指针思想,来对我们的暴力枚举做优化:
i. 先排序;
ii. 然后固定⼀个数 a :
iii. 在这个数后⾯的区间内,使用「双指针算法」快速找到两个数之和等于 -a 即可。
但是要注意,这道题里面需要有「去重」操作:
i. 找到⼀个结果之后, left 和 right 指针要「跳过重复」的元素;
ii. 当使用完⼀次双指针算法之后,固定的 a 也要「跳过重复」的元素

代码如下:

		class Solution {
		public:
		    vector<vector<int>> threeSum(vector<int>& nums)
		    {
		        // 先对数组排序
		        sort(nums.begin(), nums.end());
		
		        vector<vector<int>> ret;
		
		        // 先固定一个数,再使用双指针
		        for (int i = 0; i < nums.size() - 1; i++)
		        {
		            // 去重 nums[i] 相同的元素
		            if (i > 0 && nums[i] == nums[i - 1]) continue;
		
		            int left = i + 1, right = nums.size() - 1;
		            while (left < right)
		            {
		                if (nums[left] + nums[right] == -nums[i])
		                {
		                    ret.push_back({ nums[left],nums[right],nums[i] });
		
		                    right--, left++;
		
		                    // 去重 left 和 right
		                    while (left < right && nums[right] == nums[right + 1]) right--;
		                    while (left < right && nums[left] == nums[left - 1]) left++;
		                }
		
		                else if (nums[left] + nums[right] > -nums[i])
		                {
		                    right--;
		                }
		
		                else
		                {
		                    left++;
		                }
		            }
		
		            // 因为是排序后的数组,如果 nums[i] 大于0,后面的数都比它大,找不到两数相加等于它的负数的数,所以提前跳出环      
		            if (nums[i] > 0) break;
		        }
		        return ret;
		    }
		};

8. 四数之和

四数之和的做法也和三数之和类似,大家可以自行尝试一下,题目链接 -> Leetcode -18.四数之和

Leetcode -18.四数之和

题目:给你一个由 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]]

提示:
1 <= nums.length <= 200

  • 10^9 <= nums[i] <= 10^9
  • 10^9 <= target <= 10^9

下面直接看代码解析:文章来源地址https://www.toymoban.com/news/detail-752848.html

		class Solution {
		public:
		    vector<vector<int>> fourSum(vector<int>& nums, int target)
		    {
		        sort(nums.begin(), nums.end());
		
		        vector<vector<int>> ret;
		        int len = nums.size();
		
		        // 先固定第一个数
		        for (int i = 0; i < len - 3; i++)
		        {
		            // 去重1.
		            if (i > 0 && nums[i] == nums[i - 1]) continue;
		               
		            // 固定第二个数
		            int aim1 = target - nums[i];
		            for (int j = i + 1; j < len - 2; j++)
		            {
		                // 去重2.
		                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
		
		                // 使用双指针
		                long long aim2 = (long long)aim1 - nums[j];
		                int left = j + 1, right = len - 1;
		                while (left < right)
		                {
		                    if (nums[left] + nums[right] > aim2)
		                    {
		                        right--;
		                    }
		                    else if (nums[left] + nums[right] < aim2)
		                    {
		                        left++;
		                    }
		                    else
		                    {
		                        ret.push_back({ nums[i],nums[j],nums[left],nums[right] });
		                        left++, right--;
		
		                        // 去重3.
		                        while (left < right && nums[left] == nums[left - 1]) left++;
		                        while (left < right && nums[right] == nums[right + 1]) right--;
		                    }
		                }
		            }
		        }
		        return ret;
		    }
		};

到了这里,关于【算法专题】双指针的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法专题】双指针

    常见的双指针有两种形式,⼀种是对撞指针,⼀种是左右指针。 对撞指针:⼀般用于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终止条件⼀般是两个指针相遇或者错开(也可能

    2024年02月05日
    浏览(33)
  • 双指针算法专题

    双指针算法入门,干就完了 下面的题目都是来自灵神的基础算法精讲,有思路不清晰的地方,可以去看讲解。 灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频 (bilibili.com) 题目链接:167. 两数之和 II - 输入有序数组 - 力扣(LeetCode) 题目描述 给你一个下标从 1 开始

    2024年01月23日
    浏览(45)
  • 【算法优选】双指针专题——壹

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(46)
  • 【算法优选】双指针专题——叁

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(45)
  • 【算法专题突破】双指针 - 移动零(1)

    目录 写在前面 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 在进行了剑指Offer和LeetCode hot100的毒打之后, 我决心系统地学习一些经典算法,增强我的综合算法能力。 题目链接:283. 移动零 - 力扣(Leetcode) 读完题目大概就能明白他的意思, 就是在不改变其他数字的情况下

    2024年02月11日
    浏览(37)
  • 【算法专题突破】双指针 - 快乐数(3)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:202. 快乐数 - 力扣(Leetcode) 这道题的题目也很容易理解, 看一下题目给的示例就能很容易明白, 但是要注意一个点,最后有可能无限循环无法到达1。 这个时候我们就要想一下怎么判断他是无线循环呢? 实际

    2024年02月11日
    浏览(32)
  • 【优选算法】专题1 -- 双指针 -- 复写0

    前言: 补充一下前文没有写到的双指针入门知识:专题1 -- 双指针 -- 移动零 目录 基础入门知识: 1. 复写零(easy) 1. 题⽬链接:1089.复习0 - 力扣(LeetCode) 2. 题⽬描述: 3.算法原理: 异地操作 本地操作 【从后向前的复写过程】 整体思路: 🎯1.先找到最后一个“复写”的

    2024年04月17日
    浏览(32)
  • 【算法专题突破】双指针 - 复写零(2)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:1089. 复写零 - 力扣(Leetcode) 我先来读题, 题目的意思非常的简单,其实就是, 遇到 0 就复制一个写进数组,然后右边的元素就右移一位, 看一眼例子可以很容易理解题意。  一般像这种需要移动数组的元素

    2024年02月11日
    浏览(45)
  • 【算法专题】双指针—盛最多水的容器

      分析这个题目不难得出一个 容积公式   解法一:暴力枚举(超时) 套用上述的容积公式,使用 两个for循环 来枚举出所有可能的情况,再挑出最大值即可,但是这种写法会超时,导致不通过。时间复杂度是O(n^2) 可以自己去尝试一下。  解法二:双指针  设两个指针 left,

    2024年02月06日
    浏览(49)
  • 【算法专题突破】双指针 - 四数之和(8)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:18. 四数之和 - 力扣(Leetcode)  这道题跟三数之和也是一样的, 题目很好理解,就是四个数的和等于target的情况, 且这四个数不能重复。 首先还是暴力解法: 排序 + 暴力枚举 + set去重 我们当然是用优化的解法

    2024年02月09日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包