辽宁品牌建设促进会 网站,如何在微信公众号添加wordpress,吸引人的微信软文,前端学到什么程度可以找到工作1.简介
双指针技巧是一种常见的算法解题方法#xff0c;通过使用两个指针在数据结构上同时移动#xff0c;可以解决多种问题。这种技巧通常适用于数组、字符串和链表等数据结构#xff0c;下面我将详细介绍双指针技巧的特点和应用场景#xff1a;
特点#xff1a;
快慢…1.简介
双指针技巧是一种常见的算法解题方法通过使用两个指针在数据结构上同时移动可以解决多种问题。这种技巧通常适用于数组、字符串和链表等数据结构下面我将详细介绍双指针技巧的特点和应用场景
特点
快慢指针其中一个指针移动速度快另一个指针移动速度慢通常用于解决链表中的环路检测、链表的中间节点等问题。左右指针分别位于数据结构的两端根据问题的特点相向移动或同向移动通常用于解决数组和字符串中的搜索、反转、合并等问题。滑动窗口维护一个区间通常用于解决字符串和数组中的子串或子序列问题。
应用场景
查找/搜索对于有序数组可以使用左右指针快速查找目标元素对于无序数组可以使用左右指针来判断是否存在特定的组合或满足条件的子数组。去重/重复元素处理使用快慢指针方法对数组或链表中的重复元素进行去重或处理。反转/合并通过左右指针方法实现数组、链表的反转或合并操作例如合并两个有序链表、合并两个有序数组等。滑动窗口通过左右指针维护一个滑动窗口解决字符串和数组中的子串或子序列问题如最长无重复子串、最小覆盖子串等。
2.例题
三数之和
示例 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
class Solution {
public:vectorvectorint threeSum(vectorint nums) {int size nums.size();if (size 3) return {};vectorvectorint res;sort(nums.begin(),nums.end());for (int i 0;i size;i){if(nums[i] 0) return res;if(i 0 nums[i] nums[i - 1]) continue;int left i 1;int right size - 1;while (left right){if(nums[left] nums[right] -nums[i])right--;else if(nums[left] nums[right] -nums[i])left;else{res.push_back(vectorint{nums[i],nums[left],nums[right]});left;right--;while(leftright nums[left] nums[left - 1]) left;while(leftright nums[right] nums[right 1]) right--;}}}return res;}
};
