AI summary
type
status
date
slug
summary
category
tags
icon
password
📌
先看几道和 数组双指针技巧汇总 中例题类似的题目，巩固一下基础。

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

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
和之前的题目的区别在于保证出现不超过两次即可。在之前的解法中添加一个 count 变量记录每个数字出现的次数即可。
当碰到不同值时重置 count，相同值时 count++。赋值时要求最多已经存在一个。

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
这道题很简单，只要先把所有字符转化成小写，并过滤掉空格和标点这类字符，然后对剩下的字符执行两端向中心的双指针算法即可。

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
套用之前的 moveZeroes 函数思路当然也可以解决这道题，但要遍历两次数组，第一次把 2 移动到数组的末尾，第二次把 1 移动到末尾，只不过这个末尾不是数组的末尾，而是 2 的前面一位索引，稍微改改前文的代码并不难做到
看到三种元素的分类问题，我首先会想到两端向中心的双指针。之前的快慢指针场景，是慢指针左侧维护一个索引区间，快指针在前面探路；
那么这道题是不是可以在左右分别用指针 p0, p2 维护 0 的区间和 2 的区间，让第三个指针 p 遍历数组，把遇到的元素分类到左右两个区间中，最后中间剩下的也就是元素 1 了。这个思路只遍历一次就能得出结果。
注意 if p1 < p0: p1 = p0 ，要保证 p1 在 p0 和 p2 之间。
📌
你学会了合并有序的单链表，如果让你合并有序数组，会有哪些不同呢？

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
因为题目让我直接把结果存到 nums1 中，而 nums1 的开头有元素，如果我们无脑复制单链表的逻辑，会覆盖掉 nums1 的原始元素，导致错误。
但 nums1 后面是空的呀，所以这道题需要我们稍微变通一下：将双指针初始化在数组的尾部，然后从后向前进行合并，这样即便覆盖了 nums1 中的元素，这些元素也必然早就被用过了，不会影响答案的正确性。
📌
如果再变个花样，你是否还能依然认出这是双指针技巧合并有序数组的问题呢？

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
我们可以去寻找正负数的分界点，然后向左右扩展，执行合并有序数组的逻辑。不过还有个更好的办法，不用找正负分界点，而是直接将双指针分别初始化在 nums 的开头和结尾，相当于合并两个从大到小排序的数组，和 88 题类似。
📌
再进一步变个花样，你是否还能依然认出这是双指针技巧合并有序数组的问题呢？

360. 有序转化数组

给你一个已经 排好序 的整数数组 nums 和整数 a 、 b 、 c 。对于数组中的每一个元素 nums[i] ，计算函数值  ，请 按升序返回数组 。
977 题其实就是这道题中 a = 1, b = 0, c = 0 的特殊情况，所以这道题的关键也是在 nums 的开头和结尾设置 i, j 双指针相向而行，执行合并有序数组的逻辑，只不过这里需要考虑的情况更多了一些罢了。
关键是 nums 中的元素分布在在抛物线的两侧的情况，这就和 977 题的场景有些像，所以需要设置 i, j 双指针执行合并两个有序数组的逻辑了，当然还要考虑抛物线开口的方向。
📌
最后，来看看二维数组相关的问题。

1329. 将矩阵按对角线排序

矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。
给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。
在同一个对角线上的元素，其横纵坐标之差是相同的。直接把每个对角线的元素存到数组里，排序，然后放回二维矩阵上即可。
这个遍历对角线的代码可以作为模版背一下，省的考试的时候还要晕乎乎地手搓，费时间。

1260. 二维网格迁移

给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。
每次「迁移」操作将会引发下述活动：
  • 位于 grid[i][j]（j < n - 1）的元素将会移动到 grid[i][j + 1]。
  • 位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
  • 位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。
请你返回 k 次迁移操作后最终得到的 二维网格。
这道题有些像 151. 颠倒字符串中的单词，也要用到 二维数组的花式遍历技巧 中讲到的多次翻转的技巧。
151 题让你把句子中的所有单词位置翻转，解法思路是先翻转整个句子，然后逐一翻转每个单词。
这道题是同样的思路：你可以写一个 get 方法和 set 方法把二维数组抽象成一维数组，然后题目就变成了让你将一个一维的数组平移 k 位，相当于把前 mn - k 个元素的位置和后 k 个元素的位置对调，也可以先把整个数组翻转，再分别翻转前 mn - k 个元素和后 k 个元素，得到的结果就是题目想要的。

867. 转置矩阵

给你一个二维整数数组 matrix， 返回 matrix 的 转置矩阵 。
矩阵的 转置 是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。
这道题没啥特别的技巧，new 出来一个新的转置矩阵，其中 (x, y) 的值为原矩阵的 (y, x) 的值，直接写代码就行了。
有读者学过 二维数组的花式遍历 后可能会尝试思考如何原地转置，但是矩阵转置这种问题肯定是做不到的，因为数组的维度都不同。

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。