一 快慢指针
数组问题中比较常见的快慢指针技巧，是让你原地修改数组。
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过： 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。 示例 1： 输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
高效解决这道题就要用到快慢指针技巧：
我们让慢指针
slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。这样，就保证了
nums[0..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。int removeDuplicates(int[] nums) { if (nums.length == 0) { return 0; } int slow = 0, fast = 0; while (fast < nums.length) { if (nums[fast] != nums[slow]) { slow++; // 维护 nums[0..slow] 无重复 nums[slow] = nums[fast]; } fast++; } // 数组长度为索引 + 1 return slow + 1; }
二、左右指针的常用算法
1、二分查找
二分查找是左右指针的一种使用
int binarySearch(int[] nums, int target) { // 一左一右两个指针相向而行 int left = 0, right = nums.length - 1; while(left <= right) { int mid = (right + left) / 2; if(nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid - 1; } return -1; }
2、两数之和
要求两数之和为目标Target。
只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节
left 和 right 就可以调整 sum 的大小：3、反转数组
一般编程语言都会提供
reverse 函数，其实这个函数的原理非常简单，力扣第 344 题「反转字符串open in new window」就是类似的需求，让你反转一个 char[] 类型的字符数组，我们直接看代码吧：void reverseString(char[] s) { // 一左一右两个指针相向而行 int left = 0, right = s.length - 1; while (left < right) { // 交换 s[left] 和 s[right] char temp = s[left]; s[left] = s[right]; s[right] = temp; left++; right--; } }
4、回文串判断
boolean isPalindrome(String s) { // 一左一右两个指针相向而行 int left = 0, right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }
5、寻找最长回文串
public String longestPalindrome(String s) { String res = ""; for (int i = 0; i < s.length(); i++) { String single = findPalindrome(s, i, i); if (single.length() >= res.length()) { res = single; } String doub = findPalindrome(s, i, i + 1); if (doub.length() >= res.length()) { res = doub; } } return res; } // 寻找最长回文串 // left = right时，是奇数回文串 // left+1 = right时，是偶数回文串 public String findPalindrome(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } // 因为最后还进行了一次left--，和right++。所以需要left+1，right不需要-1. return s.substring(left + 1, right); }
三 前缀和
适用于快速、频繁的计算一个索引区间内的元素之和
1. 一维数组前缀和
303. 区域和检索 - 数组不可变 给定一个整数数组 nums，处理以下类型的多个查询: 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right 实现 NumArray 类： NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] ) 示例 1： 输入： ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] 输出： [null, 1, -1, -3]
题目要求你实现这样一个类：
class NumArray { public NumArray(int[] nums) {} /* 查询闭区间 [left, right] 的累加和 */public int sumRange(int left, int right) {} }
sumRange 函数需要计算并返回一个索引区间之内的元素和。核心思路是我们 new 一个新的数组
preSum 出来，preSum[i] 记录 nums[0..i-1] 的累加和，看图 10 = 3 + 5 + 2：
看这个
preSum 数组，如果我想求索引区间 [1, 4] 内的所有元素之和，就可以通过 preSum[5] - preSum[1] 得出。// sums[i]表示从0到i的nums的和 // preSum[i] 比sums[i]多一个前缀，即长度+1，preSum[0]=0. private int[] preSum; public NumArray(int[] nums) { preSum = new int[nums.length + 1]; // 重点：preSum[0] = 0，便于计算累加和 // 计算 nums 的累加和 for (int i = 1; i <= nums.length; i++) { preSum[i] = preSum[i - 1] + nums[i - 1]; } } public int sumRange(int left, int right) { return preSum[right + 1] - preSum[left]; }
2. 二维数组前缀和
同样可以通过前缀和来解决。
面积可以通过计算得出：
class NumMatrix { // 定义：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和 private int[][] preSum; public NumMatrix(int[][] matrix) { int m = matrix.length, n = matrix[0].length; if (m == 0 || n == 0) return; // 构造前缀和矩阵 preSum = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // 计算每个矩阵 [0, 0, i, j] 的元素和 preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1]; } } } // 计算子矩阵 [x1, y1, x2, y2] 的元素和 public int sumRegion(int x1, int y1, int x2, int y2) { // 目标矩阵之和由四个相邻矩阵运算获得 return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]; } }
四 差分数组
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
比如说，我给你输入一个数组
nums，然后又要求给区间 nums[2..6] 全部加 1，再给 nums[3..9] 全部减 3，再给 nums[0..4] 全部加 2，等等。这里就需要差分数组的技巧，类似前缀和技巧构造的
preSum 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差：构建差分数组：
int[] diff = new int[nums.length]; // 构造差分数组 diff[0] = nums[0]; for (int i = 1; i < nums.length; i++) { diff[i] = nums[i] - nums[i - 1]; }
通过这个
diff 差分数组是可以反推出原始数组 nums 的，代码逻辑如下：int[] res = new int[diff.length]; // 根据差分数组构造结果数组 res[0] = diff[0]; for (int i = 1; i < diff.length; i++) { res[i] = res[i - 1] + diff[i]; }
这样构造差分数组
diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可
原理很简单，回想
diff 数组反推 nums 数组的过程，diff[i] += 3 意味着给 nums[i..] 所有的元素都加了 3，然后 diff[j+1] -= 3 又意味着对于 nums[j+1..] 所有元素再减 3框架如下：
// 差分数组工具类 class Difference { // 差分数组 private int[] diff; /* 输入一个初始数组，区间操作将在这个数组上进行 */ public Difference(int[] nums) { assert nums.length > 0; diff = new int[nums.length]; // 根据初始数组构造差分数组 diff[0] = nums[0]; for (int i = 1; i < nums.length; i++) { diff[i] = nums[i] - nums[i - 1]; } } /* 给闭区间 [i, j] 增加 val（可以是负数）*/ public void increment(int i, int j, int val) { diff[i] += val; if (j + 1 < diff.length) { diff[j + 1] -= val; } } /* 返回结果数组 */ public int[] result() { int[] res = new int[diff.length]; // 根据差分数组构造结果数组 res[0] = diff[0]; for (int i = 1; i < diff.length; i++) { res[i] = res[i - 1] + diff[i]; } return res; } }