双指针技巧1

通常,我们只需要一个指针进行迭代,即从数组中的第一个元素开始,最后一个元素结束。然而,有时我们会使用两个指针进行迭代。
双指针1.png

例如反转数组问题中我们可以利用双指针技巧,其思想是分别将两个指针分别指向数组的开头及末尾,然后将其指向的元素进行交换,再将指针向中间移动一步,继续交换,直到这两个指针相遇。
exchangeElements.gif

使用双指针的典型场景之一是你想要 从两端向中间迭代数组。这时你可以使用双指针技巧:一个指针从头部开始,而另一个指针从尾部开始

这种技巧经常在排序数组中使用。

下面有道双指针的例题参考

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1:

输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2:

输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3:

输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示:

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

算法:

初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和,并和目标值比较。如果两个元素之和等于目标值,则发现了唯一解。如果两个元素之和小于目标值,则将左侧指针右移一位。如果两个元素之和大于目标值,则将右侧指针左移一位。移动指针之后,重复上述操作,直到找到答案。

使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉?答案是不会。假设 numbers[i]+numbers[j]=target 是唯一解,其中 0≤i<j≤numbers.length−1。初始时两个指针分别指向下标 0 和下标 numbers.length−1,左指针指向的下标小于或等于 i,右指针指向的下标大于或等于 j。除非初始时左指针和右指针已经位于下标 i 和 j,否则一定是左指针先到达下标 i 的位置或者右指针先到达下标 j 的位置。

如果左指针先到达下标 i 的位置,此时右指针还在下标 j 的右侧,sum>target,因此一定是右指针左移,左指针不可能移到 i 的右侧。

如果右指针先到达下标 j 的位置,此时左指针还在下标 i 的左侧,sum<target,因此一定是左指针右移,右指针不可能移到 j 的左侧。

由此可见,在整个移动过程中,左指针不可能移到 i 的右侧,右指针不可能移到 j 的左侧,因此不会把可能的解过滤掉。由于题目确保有唯一的答案,因此使用双指针一定可以找到答案。

代码:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return new int[]{-1, -1};
    }
}

复杂度分析:

  • 时间复杂度:O(n),其中 n 是数组的长度。两个指针移动的总次数最多为 n 次。
  • 空间复杂度:O(1)。

双指针技巧2

有时,我们可以使用两个不同步的指针来解决问题,即快慢指针。与情景一不同的是,两个指针的运动方向是相同的,而非相反。

例如:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。详细解法见下文。
如果我们没有空间复杂度上的限制,那就更容易了。我们可以初始化一个新的数组来存储答案。如果元素不等于给定的目标值,则迭代原始数组并将元素添加到新的数组中。
removeElements1.jpg

实际上,它相当于使用了两个指针,一个用于原始数组的迭代,另一个总是指向新数组的最后一个位置。

考虑空间限制
如果我们不使用额外的数组,只是在原数组上进行操作呢?

此时,我们就可以采用快慢指针的思想:初始化一个快指针 fast 和一个慢指针 slow,fast 每次移动一步,而 slow 只当 fast 指向的值不等于 val 时才移动一步。
removeElements2.gif

这是你需要使用双指针技巧的另一种非常常见的情况:同时有一个慢指针和一个快指针

解决这类问题的关键是: 确定两个指针的移动策略

与前一个场景类似,你有时可能需要在使用双指针技巧之前对数组进行排序,也可能需要运用贪心法则来决定你的运动策略。

27. 移除元素

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

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

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

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

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

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

示例 1:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

算法:

由于题目要求删除数组中等于 val 的元素,因此输出数组的长度一定小于等于输入数组的长度,我们可以把输出的数组直接写在输入数组上。可以使用双指针:右指针 right 指向当前将要处理的元素,左指针 left 指向下一个将要赋值的位置。

如果右指针指向的元素不等于 val,它一定是输出数组的一个元素,我们就将右指针指向的元素复制到左指针位置,然后将左右指针同时右移;

如果右指针指向的元素等于 val,它不能在输出数组里,此时左指针不动,右指针右移一位。

整个过程保持不变的性质是:区间 [0,left) 中的元素都不等于 val。当左右指针遍历完输入数组以后,left 的值就是输出数组的长度。

这样的算法在最坏情况下(输入数组中没有元素等于 val),左右指针各遍历了数组一次。

代码:

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

复杂度分析:

  • 时间复杂度:O(n),其中 n 为序列的长度。我们只需要遍历该序列至多两次。
  • 空间复杂度:O(1)。我们只需要常数的空间保存若干变量。

56. 合并区间

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示:

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

算法:

我们用数组 merged 存储最终的答案。

首先,我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中,并按顺序依次考虑之后的每个区间:

如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后,那么它们不会重合,我们可以直接将这个区间加入数组 merged 的末尾;

否则,它们重合,我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点,将其置为二者的较大值。

代码:

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length==0){
            return new int[0][2];
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        ArrayList<int[]> list = new ArrayList<>();

        for (int i = 0; i < intervals.length; i++) {
            int L = intervals[i][0],R=intervals[i][1];
            if (list.size()==0||list.get(list.size()-1)[1]<L){
                list.add(new int[]{L,R});
            }else {
                list.get(list.size()-1)[1]=Math.max(list.get(list.size()-1)[1],R);
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

复杂度分析:

  • 时间复杂度:O(nlogn),其中 n 为区间的数量。除去排序的开销,我们只需要一次线性扫描,所以主要的时间开销是排序的 O(nlogn)。
  • 空间复杂度:O(logn),其中 n 为区间的数量。这里计算的是存储答案之外,使用的额外空间。O(logn) 即为排序所需要的空间复杂度。

498. 对角线遍历

给你一个大小为 m x n 的矩阵 mat ,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。
diag1-grid.jpg

示例 1:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,4,7,5,3,6,8,9]

示例 2:

输入:mat = [[1,2],[3,4]]
输出:[1,2,3,4]

提示:

m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
-105 <= mati <= 105

算法:
根据题目要求,矩阵按照对角线进行遍历。设矩阵的行数为 mm, 矩阵的列数为 nn, 我们仔细观察对角线遍历的规律可以得到如下信息:

一共有 m + n - 1 条对角线,相邻的对角线的遍历方向不同,当前遍历方向为从左下到右上,则紧挨着的下一条对角线遍历方向为从右上到左下;

设对角线从上到下的编号为 i ∈ [0,m+n−2]:

当 i 为偶数时,则第 i 条对角线的走向是从下往上遍历;
当 i 为奇数时,则第 i 条对角线的走向是从上往下遍历;
当第 i 条对角线从下往上遍历时,每次行索引减 1,列索引加 1,直到矩阵的边缘为止:

当 i <m 时,则此时对角线遍历的起点位置为 (i, 0);
当 i≥m 时,则此时对角线遍历的起点位置为 (m - 1, i - m + 1);
当第 i 条对角线从上往下遍历时,每次行索引加 1,列索引减 1,直到矩阵的边缘为止:

当 i < n 时,则此时对角线遍历的起点位置为 (0, i);
当 i ≥n 时,则此时对角线遍历的起点位置为 (i - n + 1, n - 1);

代码:

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] res = new int[m * n];
        int pos=0;
        //有m+n-1条对角线
        for (int i = 0; i < m + n - 1; i++) {
            if (i%2==1){//从上到下遍历
                int x = i<n?0:i-n+1;
                int y = i<n?i:n-1;
                while (x<m&&y>=0){
                    res[pos++]=mat[x][y];
                    x++;
                    y--;
                }
            }else {//从下到上遍历
                int x = i<m?i:m-1;
                int y = i<m?0:i-m+1;
                while (y<n&&x>=0){
                    res[pos++]=mat[x][y];
                    x--;
                    y++;
                }
            }
        }
        return res;
    }
}

复杂度分析:

  • 时间复杂度:O(m×n),其中 m 为矩阵行的数量,n 为矩阵列的数量。需要遍历一遍矩阵中的所有元素,需要的时间复杂度为 O(m×n)。
  • 空间复杂度:O(1)。除返回值外不需要额外的空间。
最后修改:2022 年 12 月 20 日
如果觉得我的文章对你有用,请随意赞赏