双指针的话,其实是数组的操作的一种技巧,“指针”其实就是指向数组下标索引。

在最开始的时候,我们也用过这种双指针,不过并没有意识到这个名字,并且也没有什么优化。

// 这个双重循环也是双指针的一种。
for(int i = 0;i < n;i++){
    for(int j = 0;j < n;j++){
        // ...
    }
}

在做题里面,双指针的方式常常是一头一尾一快一慢……并且常常和排序一起出现。
下面展示几道典型的双指针题目,也是一种题型的记录。
PS:记录的题目尽量是单纯只用双指针题目,当然也不大可能,使用的算法往往不止一种,但是有一个大思路,题目也就迎刃而解了。有时候再继续补,慢慢刷……

11. 盛最多水的容器

15. 三数之和

16. 最接近的三数之和

19. 删除链表的倒数第 N 个结点

26. 删除有序数组中的重复项

27. 移除元素

141. 环形链表

881. 救生艇


11. 盛最多水的容器

给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器。
question_11.jpg

这个题目,如果之前没有见过的话,很难想象这种双指针的解法。

但自己模拟一下,又能知道它想表达的意思。

简单表述就是,ans = min(左柱高度, 右柱高度) * 两柱距离,那自然就是使用双指针,一左一右,每移动一步就计算一次结果,直到中间相遇为止。

问题又来了,怎么向中间移动呢?或者说移动的标准是什么呢?

再看回上面容纳水量的表述,可以知道两柱距离是确定的,因为向里面移动,距离肯定会-1;左右柱高度也知道,移动左柱还是移动右柱?

看哪根柱低,就移动哪根

ummmmm,希望结果最大,相乘的数肯定越大越好,向左或向右移动后的数的大小未知,但是如果相乘的数变小了,那面积肯定小了,所以选择留下大的那个,抛弃小的那个让它移动。

class Solution {
    public int maxArea(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int ans = 0;
        while(left < right){
            // 计算容量,更新结果
            ans = Math.max(ans,
                Math.min(height[left], height[right]) * (right - left));
            // 移动小的,留下大的乘
            if(height[left] <= height[right]){
                left++;
            }else{
                right--;
            }
        }
        return ans;
    }
}

15. 三数之和

在做这个题目之前,我改了一个1. 两数之和的题目,看清楚题目描述,然后再做题!(修改过的)

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回这两个整数

你可以假设每种输入只会对应一个答案。

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

只会存在一个有效答案
进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

典型的双指针题目啊!(我把它返回下标改成了返回值)

首先把它进行排序,然后势必会出现:左边的元素小、右边的元素大。

然后再用两个指针指向数组的两端,一小一大。

验证结果,如果大了,右指针就往左移;如果小了,左指针就往右称。因为这种操作可以让最后的和的结果更接近target。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int sum = nums[left] + nums[right];
            if(sum == target){
                return new int[]{nums[left], nums[right]};
            }else if(sum < target){
                left++;
            }else if(sum > target){
                right--;
            }
        }
        return null;
    }
}

然后再看这道题:

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

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

示例 1:

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

输入:nums = []
输出:[]
示例 3:

输入:nums = [0]
输出:[]

提示:

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

这个题目,是不是一开始就是想这样做。

for(int i = 0;i < n;i++){
    for(int j = 0;j < m;j++){
        for(int k = 0;k < z;k++){
            // ...
        }
    }
}

但是如果你知道上面那个改编过的两数之和,你就会有不一样的想法。

先把数组排序,然后循环。但是需要三层循环吗?

首先明确我们的目标:a + b + c = 0

第一层指向的是a,然后我们的目标不就变成了:b + c = -a

这不就是上面Two Sum的题目吗?两数之和的target变成了-a。

这个思路可以把原来三层循环$O(N3)$降成$O(N2)$。

最后再解决一些小细节,这道题目就差不多了。

首先,按照上面说的框架,你可以写出这样的代码出来。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return res;
        }
        Arrays.sort(nums);
        for(int first = 0;first < nums.length;first++){
            int second = first + 1;
            int third = nums.length - 1;
            while(second < third){
                int sum = nums[first] + nums[second] + nums[third];
                if(sum == 0){
                    res.add(Arrays.asList(nums[first], nums[second], nums[third]));
                    second++;
                    third--;
                }else if(sum < 0){
                    second++;
                }else if(sum > 0){
                    third--;
                }
            }
        }
        return res;
    }
}

这个可以解决很大一部分问题,但是没有处理重复的细节

image20210614201440952.png

因此还需要添加一些判断去重的操作,这里就不再细讲了,因为大方向的双指针已经解决,剩下的看代码写得怎样了……

它的要求是答案中不可以包含重复的三元组。

所以只要有重复的就直接跳过

首先,在第一层循环里,除了第一次外,若当前值与上一个值相同,那就跳过它。

if(first != 0 && nums[first] == nums[first - 1]){
    continue;
}

双指针那部分,找到结果后,看第二个值和第三个值“接下来的值”是否和它们相等,若相等,则跳过。

比如,内层双指针的循环中,左指针是要一直++向右移动的嘛,如果要移动的下一个值和当前的值一样,那就跳过它!因为下一次若还是这个值,就可能造成相同的结果。右指针则同理。(注意边界。)

while(second < third && nums[second] == nums[second + 1]){
    second++;
}
while(second < third && nums[third] == nums[third - 1]){
    third--;
}

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示:

3 <= nums.length <= 103
-10
3 <= nums[i] <= 103
-10
4 <= target <= 10^4

这个题目简直就是和我改编的的两数之和一模一样,就是利用排序+双指针让时间复杂度降了一级,变成了$O(N^2)$。

感觉有了双指针的思路,这类题目做起来就是得心应手。

当然,我也有很多细节没有讲解,因为只是想体现一下双指针而言,想要更多的解答还得去评论区或者题解处。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int first = 0;first < nums.length;first++){
            int second = first + 1;
            int third = nums.length - 1;
            while(second < third){
                int sum = nums[first] + nums[second] + nums[third];
                // 每次遍历都计算一次结果,比较一下哪次更近
                if(Math.abs(sum - target) < Math.abs(ans - target)){
                    ans = sum;
                }
                if(sum > target){
                    third--;
                }else if(sum < target){
                    second++;
                }else if(sum == target){
                    return target;
                }
            }
        }
        return ans;
    }
}

19. 删除链表的倒数第 N 个结点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

**进阶:**你能尝试使用一趟扫描实现吗?

remove_ex1.jpg

其实关于链表的操作,有很多都是利用双指针来解决的,因为链表的特殊性,都是靠.next来遍历的。

这里很明显就要使用一种叫做快慢指针的技巧来完成。

单向链表只能往前走,不能往后走,需要倒数第n个,按照正常的遍历肯定不行。

但是我们可以使用一个快指针,让它先走n步,然后再定义一个指针和它慢慢走,等快指针走到尽头的时候,慢指针刚好到达倒数第n个元素的前一个,就可以删掉它了。

PS:注意空指针……

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) { 
        ListNode fast = head;
        ListNode slow = head;
        // 快指针先走n步
        for(int i = 0;i < n;i++){
            fast = fast.next;
        }
        // 特殊情况,有一个仅是要删的那一个
        if(fast == null){
            return head.next;
        }
        // 快慢指针一起走
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        // 慢指针的下一个即为要删除的元素
        slow.next = slow.next.next;
        return head;
    }
}

26. 删除有序数组中的重复项

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

既然提示了是排序数组,那就……明显的双指针了,当然还得想清楚怎么个双指针法,最好画画图。

一个指针维护不重复的元素片段,另一个指针遍历全部的数组,它就是走得很“快”,向前找元素。

如果见到新的元素(就是不同的元素)就覆盖回第一个指针处;若遇到相同的就不管它。

这样,返回维护不重复元素的指针的下标,就是所要的长度。

class Solution {
    public int removeDuplicates(int[] nums) {
        int left = 0;
        for(int right = left + 1;right < nums.length;right++){
            if(nums[left] != nums[right]){
                nums[++left] = nums[right];
            }
        }
        return ++left;
    }
}

27. 移除元素

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

其实我发现这个确实是简单题,但是就……因为用了for,导致自己感觉有点乱。

定义两个指针吧,用while控制,这样就会清晰很多!

一个指针跑得“快”,用于遍历所有的元素;另一个指针跑得“慢”,用于维护移除后的数组。

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = 0;
        while(right < nums.length){
            // 值相同,则不用管,继续遍历
            if(nums[right] == val){
                right++;
            // 值不同,则覆盖掉,两个指针都向前
            }else if(nums[right] != val){
                nums[left++] = nums[right++]; 
            }
        }
        return left;
    }
}

这里还能进行一些优化,就是把它从后往前覆盖,避免了多个覆盖的问题。

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while(left < right){
            if(nums[left] == val){
                nums[left] = nums[--right];
            }else {
                left++;
            }
        }
        return left;
    }
}

141. 环形链表

给定一个链表,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

如果链表中存在环,则返回 true 。 否则,返回 false 。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这个是典型的一快一慢、快慢指针的用法。

如果成环了,那遍历

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 快慢指针
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            // 相遇即有环
            if(fast == slow){
                return true;
            }
        }
        // 走到尽头即表明它没有环
        return false;
    }
}

881. 救生艇

第 i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

其实这个题,除了双指针外还有贪心的思想。
首先题目保证了每个人都能被船载,然后它需要载到每一个人所需的最小船数,则肯定是想最重的和最轻的(或者是比较轻的)一起走。
比如四个人[a1, a2, a3, a4],若a1 + a4 <= limit,而a2 + a4 <= limit
根据一般的想法,肯定是想让a4带a2走,然后让最小的a1再匹配上一些大的。
但是想想,既然a2 + a4 <= limit,但是a3 < a4,所以a2 + a3 <= limit肯定成立,因此只要排序后,一大配一小就行。

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        if(people == null || people.length == 0){
            return 0;
        }
        // 排序,保证体重升序,方便双指针
        Arrays.sort(people);
        int left = 0;
        int right = people.length - 1;
        int ans = 0;
        while(left <= right){
            // 最重的能否和较轻的走
            if(people[left] + people[right] <= limit){
                left++;
                right--;
            }else{
                // 重的自己走
                right--;
            }
            ans++;
        }
        return ans; 
    }
}