双指针
删除有序数组的重复项
int removeDuplicates(int[] nums) {
// 特殊情况
if (nums.length == 0) {
return 0;
}
// 1. 定义快慢指针
int slow = 0, fast = 0;
// 2. 在快指针指向数组范围内操作
while (fast < nums.length) {
// 2.2 当快慢指针数字不同时，覆盖原有数字
if (nums[slow] != nums[fast]) {
slow++;
nums[slow] = nums[fast];
}
// 2.1 当nums[slow] == nums[fast]时跳到下一个
fast++;
}
// 3. 返回唯一的个数为 slow + 1
return slow + 1;
}
移除元素
int removeElement(int[] nums, int val) {
// 1. 定义快慢指针
int slow = 0, fast = 0;
// 2. 在快指针指向数组范围内操作
while (fast < nums.length) {
// 2.2 当指针数字与val不同时，覆盖数字
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
// 2.1 当nums[fast] == val的时候跳到下一个
fast++;
}
return slow;
}
移动零
void moveZeroes(int[] nums) {
// 1. 沿用上一题解，先把0全部去掉，其余顺序不变
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
// 2. 最后把去掉的位置都填上0
for (; slow < nums.length; slow++) {
nums[slow] = 0;
}
}
二分查找
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;
}
两数之和 II - 输入有序数组
LeetCode 167. 两数之和 II - 输入有序数组
int[] twoSum(int[] numbers, int target) {
// 1. 由于给定数组从下标1开始，则可以先按照正常下标运算，最后返回值+1即可
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
// 2.1 当和与目标数相等时，返回数组
if (sum == target) {
return new int[]{left + 1, right + 1};
}
// 2.2 当和比目标数小时，左边指针右移
else if (sum < target) {
left++;
}
// 2.3 当和比目标数大时，右边指针左移
else {
right--;
}
}
// 3. 不存在时的情况
return new int[]{-1, -1};
}
反转字符串
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
最长回文子串
String longestPalindrome(String s) {
String ret = "";
// 1. 从第一个字符开始遍历，找到最长的回文字符串
for (int i = 0; i < s.length(); i++) {
// 2.1 有两种情况，可能是偶数个，也可能是奇数个
String a = palindrome(s, i, i); // 奇数长度回文
String b = palindrome(s, i, i + 1); // 偶数长度回文
// 2.2 既是奇数偶数的长度比较，同时也是每次遍历字符串的长度比较
ret = ret.length() > a.length() ? ret : a;
ret = ret.length() > b.length() ? ret : b;
}
return ret;
}
// 寻找最长回文字符串，指针从中间开始向左右扩散
String palindrome(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
// 在这里，l和r由于判断逻辑会左右多走一步
// 由于substring的范围是[left, right)
// 因此最长回文字符串是s.substring(l + 1, r)
return s.substring(l + 1, r);
}
花式遍历
旋转图像
核心技巧：顺时针旋转 = 先沿主对角线翻转矩阵 + 再沿垂直中线左右翻转，这种方法无需额外空间，效率更高。
void rotate(int[][] matrix) {
// 以主对角线翻转二维数组
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) { // j从i开始，避免重复翻转
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
// 左右旋转每一行数组
for (int[] arr : matrix) {
reverse(arr);
}
}
// 辅助函数：反转一维数组
void reverse(int[] arr) {
int i = 0, j = arr.length - 1;
while (i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
补充：逆时针旋转图像
核心技巧：逆时针旋转 = 先沿副对角线翻转矩阵 + 再沿垂直中线左右翻转。
void rotate(int[][] matrix) {
int n = matrix.length;
// 沿副对角线翻转矩阵
for (int i = 0; i < n; i++) {
for (int j = n - i - 1; j >= 0; j--) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][n - 1 - i];
matrix[n - 1 - j][n - 1 - i] = tmp;
}
}
// 左右旋转每一行数组
for (int[] arr : matrix) {
reverse(arr);
}
}
// 辅助函数：反转一维数组
void reverse(int[] arr) {
int i = 0, j = arr.length - 1;
while (i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
螺旋矩阵
核心思路：定义边界，逐步收缩。设置左、右、上、下四个边界，按照“从左到右→从上到下→从右到左→从下到上”的顺序遍历，每完成一轮遍历就收缩对应边界，直到遍历完所有元素。
List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int left = 0, right = n - 1; // 左右边界
int top = 0, bottom = m - 1; // 上下边界
List<Integer> list = new LinkedList<>();
while (list.size() < m * n) { // 遍历整个数组，直到收集完所有元素
// 1. 从左到右遍历上边界
if (top <= bottom) {
for (int i = left; i <= right; i++) {
list.add(matrix[top][i]);
}
top++; // 上边界下移
}
// 2. 从上到下遍历右边界
if (left <= right) {
for (int i = top; i <= bottom; i++) {
list.add(matrix[i][right]);
}
right--; // 右边界左移
}
// 3. 从右到左遍历下边界
if (top <= bottom) {
for (int i = right; i >= left; i--) {
list.add(matrix[bottom][i]);
}
bottom--; // 下边界上移
}
// 4. 从下到上遍历左边界
if (left <= right) {
for (int i = bottom; i >= top; i--) {
list.add(matrix[i][left]);
}
left++; // 左边界右移
}
}
return list;
}
nSum问题
两数之和 II - 输入有序数组
LeetCode 167. 两数之和 II - 输入有序数组
int[] twoSum(int[] nums, int target) {
Arrays.sort(nums);
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
if (sum < target) {
lo++;
} else if (sum > target) {
hi--;
} else {
return new int[]{nums[lo], nums[hi]};
}
}
return new int[]{-1, -1};
}
两数之和进阶
需求：输入一个有序数组，返回所有和为 target 的不重复数对（如 nums = [1,3,1,2,2,3], target = 4，返回 [[1,3],[2,2]]）。
核心难点：跳过重复元素，避免出现 [1,3] 和 [3,1]、[2,2] 和 [2,2] 这样的重复结果。
List<List<Integer>> twoSumTarget(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int leftVal = nums[lo], rightVal = nums[hi];
if (sum < target) {
// 跳过左侧重复元素
while (lo < hi && nums[lo] == leftVal) lo++;
} else if (sum > target) {
// 跳过右侧重复元素
while (lo < hi && nums[hi] == rightVal) hi--;
} else {
// 记录符合条件的数对
res.add(new ArrayList<>(Arrays.asList(leftVal, rightVal)));
// 跳过两侧重复元素
while (lo < hi && nums[lo] == leftVal) lo++;
while (lo < hi && nums[hi] == rightVal) hi--;
}
}
return res;
}
三数之和
核心思路：拆解问题，将三数之和拆分为“一个固定数 + 两数之和”，利用两数之和的解法完成，同时注意去重。
List<List<Integer>> threeSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> ret = new ArrayList<>();
// 1. 遍历固定第一个数
for (int i = 0; i < nums.length; i++) {
// 调用两数之和解法，寻找和为 target - nums[i] 的数对
List<List<Integer>> tmp = twoSumTarget(nums, i + 1, target - nums[i]);
for (List<Integer> tuple : tmp) {
// 2. 组合三数并加入结果集
tuple.add(nums[i]);
ret.add(tuple);
}
// 3. 跳过第一个数的重复元素，避免重复结果
while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
}
return ret;
}
// 两数之和（带起始下标，去重）
List<List<Integer>> twoSumTarget(int[] nums, int start, int target) {
List<List<Integer>> ret = new ArrayList<>();
int lo = start, hi = nums.length - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int leftVal = nums[lo], rightVal = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == leftVal) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == rightVal) hi--;
} else {
ret.add(new ArrayList<>(Arrays.asList(leftVal, rightVal)));
while (lo < hi && nums[lo] == leftVal) lo++;
while (lo < hi && nums[hi] == rightVal) hi--;
}
}
return ret;
}
四数之和
核心思路：递归拆解，将四数之和拆分为“一个固定数 + 三数之和”，再将三数之和拆分为“一个固定数 + 两数之和”，逐层解决，同时注意处理数值溢出问题。
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> ret = new ArrayList<>();
// 1. 遍历固定第一个数
for (int i = 0; i < nums.length; i++) {
// 调用三数之和解法，寻找和为 target - nums[i] 的三元组
List<List<Integer>> tmp = threeSumTarget(nums, i + 1, (long) target - nums[i]);
for (List<Integer> tuple : tmp) {
// 2. 组合四数并加入结果集
tuple.add(nums[i]);
ret.add(tuple);
}
// 3. 跳过第一个数的重复元素，避免重复结果
while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
}
return ret;
}
// 三数之和（带起始下标，处理溢出）
List<List<Integer>> threeSumTarget(int[] nums,int start, long target) {
List<List<Integer>> ret = new ArrayList<>();
// 1. 遍历固定第二个数
for (int i = start; i < nums.length; i++) {
// 调用两数之和解法，寻找和为 target - nums[i] 的数对
List<List<Integer>> tmp = twoSumTarget(nums, i + 1, target - nums[i]);
for (List<Integer> tuple : tmp) {
// 2. 组合三数并加入结果集
tuple.add(nums[i]);
ret.add(tuple);
}
// 3. 跳过第二个数的重复元素，避免重复结果
while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
}
return ret;
}
// 两数之和（带起始下标，处理溢出）
List<List<Integer>> twoSumTarget(int[] nums, int start, long target) {
List<List<Integer>> ret = new ArrayList<>();
int lo = start, hi = nums.length - 1;
while (lo < hi) {
long sum = (long) nums[lo] + nums[hi];
int leftVal = nums[lo], rightVal = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == leftVal) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == rightVal) hi--;
} else {
ret.add(new ArrayList<>(Arrays.asList(leftVal, rightVal)));
while (lo < hi && nums[lo] == leftVal) lo++;
while (lo < hi && nums[hi] == rightVal) hi--;
}
}
return ret;
}
前缀和
区域和检索-数组不可变
普通解法
如果不使用前缀和，每次查询都需要遍历区间求和，sumRange() 方法的时间复杂度为 O(N)，多次查询时性能开销过大。
class NumArray {
private int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += nums[i];
}
return sum;
}
}
前缀和解法
核心思路：预处理前缀和数组，提前计算从数组起始位置到每个下标位置的元素和，查询时只需通过前缀和数组的差值快速得到区间和，sumRange() 方法的时间复杂度优化为 O(1)。
class NumArray {
// 前缀和数组：preSum[i] 表示 nums[0..i-1] 的元素和
int[] preSum;
public NumArray(int[] nums) {
preSum = new int[nums.length + 1];
// 构建前缀和数组
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
}
// 查询 [left, right] 区间的元素和
public int sumRange(int left, int right) {
return preSum[right + 1] - preSum[left];
}
}
二维区域和检索 - 矩阵不可变
核心思路：预处理二维前缀和数组，任意子矩阵的元素和可以通过二维前缀和数组的四个角点差值计算得到，避免重复遍历子矩阵。
class NumMatrix {
// 二维前缀和数组：preSum[i][j] 表示矩阵 [0..i-1][0..j-1] 的元素和
int[][] preSum;
public NumMatrix(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
preSum = new int[0][0];
return;
}
int m = matrix.length, n = matrix[0].length;
preSum = new int[m + 1][n + 1];
// 构建二维前缀和数组
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] -
preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
// 查询子矩阵 [row1, col1] 到 [row2, col2] 的元素和
public int sumRegion(int row1, int col1, int row2, int col2) {
return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] -
preSum[row2 + 1][col1] + preSum[row1][col1];
}
}