【寻找one piece的算法之路】——双指针算法！他与她是否会相遇呢？
💐个人主页：初晴~
📚相关专栏：寻找one piece的刷题之路
什么是双指针算法
双指针算法是一种常用的编程技巧，尤其在处理数组和字符串问题时非常有效。这种方法的核心思想是使用两个指针来遍历数据结构，这两个指针通常分别位于数据结构的起始位置或某些特定位置，通过移动这两个指针来达到解决问题的目的。双指针算法可以显著减少时间复杂度，使其从O(n2)O(n2)降低到O(n)O(n)，甚至在某些情况下可以达到O(logn)O(logn)。
- 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
- 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循 环），也就是：
- left == right （两个指针指向同⼀个位置）
- left > right （两个指针错开）
一、复写零
题目描述：
题目分析：
题目的意思就是遍历原数组，每遇到一次0，就将后面所有的数水平向右移动一位，并再插入一个0，最后仍丢弃溢出的数据，仍取原来的数组长度的数据。
分析：
我们先初始化两个指针 cur = 0 ， dest = -1
判断 cur 位置的元素:◦ 如果是 0 的话， dest 往后移动两位；◦ 否则， dest 往后移动⼀位。
注意：
要判断 dest 是否越界到 n 的位置：如果越界，执⾏下⾯三步：
- n - 1 位置的值修改成 0 ；
- cur 向移动⼀步；
- dest 向前移动两步。
2.然后从后向前进⾏复写操作
从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：
代码实现：
class Solution {
public void duplicateZeros(int[] arr) {
int len=arr.length,cur=0,dest=-1;
while(cur<len){
if(arr[cur]==0){
dest+=2;
}else{
dest++;
}
if(dest==len-1)break;
if(dest>len-1){
arr[len-1]=0;
cur--;
dest=len-2;
break;
}
cur++;
}
if(dest==cur)return;
while(cur>=0){
if(arr[cur]!=0){
arr[dest--]=arr[cur--];
}else{
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
}
}
二、盛⽔最多的容器
题目描述：
题目分析：
v = (right - left) * min( height[right], height[left])
- 容器的宽度⼀定变⼩。
- 由于左边界较⼩，决定了⽔的⾼度。如果改变左边界，新的⽔⾯⾼度不确定，但是可能会超过原来左边界的柱⼦⾼度，因此容器的容积可能会增⼤。
- 如果改变右边界，⽆论右边界移动到哪⾥，新的⽔⾯的⾼度⼀定不会超过左边界，也就是不会超过现在的⽔⾯⾼度，但是由于容器的宽度减⼩，因此容器的容积⼀定会变⼩的。
- 当我们不断重复上述过程，每次都可以舍去⼤量不必要的枚举过程，直到 left 与 right 相遇。期间产⽣的所有的容积⾥⾯的最⼤值，就是最终答案。
代码实现：
class Solution {
public int maxArea(int[] height) {
int l=0,r=height.length-1,max=0,t;
while(l<r){
if(height[l]<height[r]){
t=height[l]*(r-l);
l++;
}else{
t=height[r]*(r-l);
r--;
}
if(max<t)max=t;
}
return max;
}
}
三、有效三⻆形的个数
题目描述：
题目分析：
首先我们得知道，三条边能构成三角形的充要条件是：任意两边之和大于第三边。
不过事实上，我们只要保证两条短边和大于最长边即可。
因此，我们可以先将数组从小到大进行排序，接着用一个指针 j 固定一个「最⻓边」，然后在⽐这条边⼩的有序数组中找出⼀个⼆元组，使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的，我们可以利⽤「对撞指针」来优化
设最⻓边枚举到 j 位置，区间 [left, right] 是 j 位置左边的区间（也就是⽐它⼩的区间）：
- 如果 nums[left] + nums[right] > nums[i] ：
说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐ nums[j] ⼤的⼆元组
则满⾜条件的有 right - left 种
此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进⼊下⼀轮判断
- 如果 nums[left] + nums[right] <= nums[i] ：
说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满⾜条件的⼆元组
left 位置的元素可以舍去， left++ 进⼊下轮循环
代码实现：
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int sum=0;
for(int j=nums.length-1;j>=2;j--){
int l=0,r=j-1;
while(l<r){
if(nums[l]+nums[r]>nums[j]){
sum=sum+r-l;
r--;
}else{
l++;
}
}
}
return sum;
}
}
四、三数之和
题目描述：
题目分析：
这题其实与上一题十分相似，都是要找一个满足一定条件的三元组，因此同样，我们可以采用先排序，接着用一个指针 j 固定一个数 a，接着在之后的区间内，利用双指针算法找到两数之和等于-a即可
需要注意的是，题目要求进行「去重」操作：
- 找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
- 当使⽤完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素
代码实现：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
int n=nums.length;
for(int j=0;j<n;){
if(nums[j]>0)break;
int l=j+1,r=n-1;
int target=-nums[j];
while(l<r){
int sum=nums[l]+nums[r];
if(sum==target){
ans.add(new ArrayList<Integer>(Arrays.asList(nums[l],nums[r],
nums[j])));
if(nums[r]==nums[l])break;
l++;
r--;
while(l<r&&nums[r+1]==nums[r])r--;
while(l<r&&nums[l-1]==nums[l])l++;
}else if(sum>target){
r--;
}else{
l++;
}
}
j++;
while(j<n&&nums[j]==nums[j-1])j++;
}
return ans;
}
}
五、四数之和
题目描述：
题目描述：
这题的思想其实也与三数之和类似，我们只需要先排序，再用一个指针 i 固定一个数 a，在这个数 a 的后⾯区间上，利⽤「三数之和」找到三个数，使这三个数的和等于 target - a 即可
代码实现：
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
int n=nums.length;
long t,q;
Arrays.sort(nums);
List<List<Integer>> ans=new ArrayList<List<Integer>>();
for(int i=0;i<n;){
t=target;
t-=nums[i];
//if(t<0)return ans;
for(int j=i+1;j<n;){
q=t;
q-=nums[j];
int l=j+1,r=n-1;
while(l<r){
int sum=nums[l]+nums[r];
if(sum==q){
List<Integer> list=new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[l]);
list.add(nums[r]);
ans.add(list);
l++;
r--;
while(l<r&&nums[l]==nums[l-1])l++;
while(l<r&&nums[r]==nums[r+1])r--;
}else if(sum>q)r--;
else l++;
}
j++;
while(j<n&&nums[j]==nums[j-1])j++;
}
i++;
while(i<n&&nums[i]==nums[i-1])i++;
}
return ans;
}
}
总结
双指针技巧的关键点：
- 初始化：通常一个指针指向序列的开始位置，另一个指针指向序列的结束位置或某个特定位置。
- 移动规则：根据问题的具体情况定义指针的移动规则，如当条件不满足时向前或向后移动。
- 更新状态：在每次移动指针之后更新当前的状态，如累加、记录最大值等。
- 退出条件：当两个指针相遇或某个指针超出界限时结束循环。
双指针算法是一种简单而有效的算法技巧，通过维护两个指针的状态来简化问题的复杂度。合理地运用双指针法，可以帮助我们在处理数组和字符串问题时更加高效地达成目标。
那么本篇文章就到此为止了，如果觉得这篇文章对你有帮助的话，可以点一下关注和点赞来支持作者哦。如果有什么讲的不对的地方欢迎在评论区指出，希望能够和你们一起进步✊
原文地址：https://blog.csdn.net/acm_pn/article/details/142642649
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！