Loading... # 双指针技巧1 通常,我们只需要一个指针进行迭代,即从数组中的第一个元素开始,最后一个元素结束。然而,有时我们会使用两个指针进行迭代。  例如反转数组问题中我们可以利用双指针技巧,其思想是分别将两个指针分别指向数组的开头及末尾,然后将其指向的元素进行交换,再将指针向中间移动一步,继续交换,直到这两个指针相遇。  使用双指针的典型场景之一是你想要 **从两端向中间迭代数组**。这时你可以使用双指针技巧:**一个指针从头部开始,而另一个指针从尾部开始**。 这种技巧经常在排序数组中使用。 下面有道双指针的例题参考 # [167. 两数之和 II - 输入有序数组](https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/) 给你一个下标从 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 的元素,并返回移除后数组的新长度。详细解法见下文。 如果我们没有空间复杂度上的限制,那就更容易了。我们可以初始化一个新的数组来存储答案。如果元素不等于给定的目标值,则迭代原始数组并将元素添加到新的数组中。  实际上,它相当于使用了两个指针,一个用于原始数组的迭代,另一个总是指向新数组的最后一个位置。 考虑空间限制 如果我们不使用额外的数组,只是在原数组上进行操作呢? 此时,我们就可以采用快慢指针的思想:初始化一个快指针 fast 和一个慢指针 slow,fast 每次移动一步,而 slow 只当 fast 指向的值不等于 val 时才移动一步。  这是你需要使用双指针技巧的另一种非常常见的情况:**同时有一个慢指针和一个快指针**。 解决这类问题的关键是: **确定两个指针的移动策略**。 与前一个场景类似,你有时可能需要在使用双指针技巧之前对数组进行排序,也可能需要运用贪心法则来决定你的运动策略。 # [27. 移除元素](https://leetcode.cn/problems/remove-element/) 给你一个数组 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. 合并区间](https://leetcode.cn/problems/merge-intervals/) 以数组 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. 对角线遍历](https://leetcode.cn/problems/diagonal-traverse/) 给你一个大小为 m x n 的矩阵 mat ,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。  **示例 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 <= mat[i][j] <= 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 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得我的文章对你有用,请随意赞赏