SYSTEM
LeetCode 5道高频数组题 完整总结
src/content/notes/algorithm/数组双指针.md LeetCode 5道高频数组题 完整总结
包含:两数之和、26删除有序数组重复项、283移动零、11盛最多水容器、15三数之和 分三块:核心思路、标准代码、必踩细节,秋招笔试面试直接背诵
一、1. 两数之和
1. 核心思路
数组短板:只知道数值找下标需要遍历O(n) 用哈希表空间换时间,一次遍历完成:
- 遍历当前数
nums[i],计算目标配对值need = target - nums[i] - 查表:如果存在need,直接返回
[map.get(need), i] - 不存在就把
(当前值,下标)存入map,留给后续数字匹配
- 时间O(n),空间O(n)
- 暴力双层循环O(n²),数组遍历太慢,不推荐
2. 标准代码
import java.util.HashMap;
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int need = target - nums[i];
if(map.containsKey(need)){
return new int[]{map.get(need), i};
}
map.put(nums[i], i);
}
return new int[]{};
}
}
3. 关键细节(踩坑点)
- 先判断containsKey,后put 如果先存再判断,会取到当前自身,出现
[i,i]重复下标错误; - HashMap存
key=数值,value=下标,因为我们需要通过值反向查位置; - 题目保证唯一解,循环内一定return,末尾空数组仅语法补齐。
二、26. 删除有序数组中的重复项
1. 核心思路:同向快慢双指针(原地覆盖)
有序数组重复元素相邻,原地修改不能新开数组:
- slow慢指针:维护无重复有效区间末尾
- fast快指针:遍历全数组,筛选不重复的新元素
- fast找到和slow不相等的数字,slow先前进一位
- 将fast的值覆盖到slow位置
- 最终有效长度 = slow + 1
- 时间O(n),空间O(1) 纯原地操作
2. 标准代码
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length == 0) return 0;
int slow = 0;
for(int fast = 1; fast < nums.length; fast++){
if(nums[fast] != nums[slow]){
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
}
3. 关键细节
- 边界:数组为空直接返回0;
- slow初始0,fast从1开始,对比相邻元素;
- 只覆盖前slow+1位,后面剩余数字题目忽略不用清理;
- 模板通用:筛选有效元素向前覆盖,和283移动零是一套模板。
三、283. 移动零
1. 核心思路:同向快慢双指针(原地分离有效值)
要求:原地操作、非零数字相对顺序不变
- slow:记录下一个非0该存放的位置
- fast:遍历筛选所有非0数字
- fast遇到非0,覆盖到slow位置,slow++
- 一轮遍历后
[0,slow)全是非0,第二轮循环把slow到末尾全部填0 进阶交换写法:找到非0直接交换slow/fast,无需二次置0
2. 标准代码(两段式,最好理解)
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
// 第一步:把所有非0前移
for(int fast = 0; fast < nums.length; fast++){
if(nums[fast] != 0){
nums[slow++] = nums[fast];
}
}
// 第二步:末尾补0
for(int i = slow; i < nums.length; i++){
nums[i] = 0;
}
}
}
3. 关键细节
- 不能新建数组存储非0,违反原地操作要求;
- 必须先移非0再补0,保证原有数字相对顺序不乱;
- 和26题模板统一:fast筛选有效元素,slow维护有效区间;
- 不能用左右对撞双指针:会打乱非零元素原有顺序。
四、11. 盛最多水的容器
1. 核心思路:左右对撞双指针(压缩宽度求最大面积)
面积公式:宽 × 矮边高度
- left在最左,right在最右,初始宽度最大
- 计算当前面积,更新最大值
- 移动高度更小的一侧指针:只有移动矮边,才有可能提升高度、得到更大面积;移动高边只会宽度变小,面积必然更小
- 两指针相遇结束遍历
- 时间O(n),空间O(1)
2. 标准代码
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int max = 0;
while(left < right){
int w = right - left;
int h = Math.min(height[left], height[right]);
max = Math.max(max, w * h);
if(height[left] < height[right]){
left++;
}else{
right--;
}
}
return max;
}
}
3. 关键细节
- 面积由较短柱子决定,高柱子再高也留不住水;
- 指针移动规则:谁矮移谁,是本题最优解核心;
- 暴力两层循环枚举所有左右组合O(n²),大数据直接超时;
- 对比同向双指针:本题是左右收缩对撞,前两题是从前到后同向遍历。
五、15. 三数之和(最优:排序+同向双指针)
1. 核心思路
- 先排序数组,让重复数字相邻,方便去重;
- 外层循环固定第一个数nums[i],目标转化为:在i右侧区间找两数之和 =
-nums[i]; - i右侧用左右对撞双指针找两数,和为0记录答案;
- 三层去重保证结果无重复三元组:
- 外层i去重:跳过和前一个相等的nums[i]
- 内层left去重:跳过左侧重复值
- 内层right去重:跳过右侧重复值
- 时间O(n²),排序开销O(nlogn),哈希解法去重复杂,不推荐面试写
2. 标准代码
import java.util.*;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
for(int i = 0; i < n - 2; i++){
// 外层i去重
if(i > 0 && nums[i] == nums[i-1]) continue;
// 优化:当前数>0,后面全更大,不可能和为0
if(nums[i] > 0) break;
int left = i + 1;
int right = n - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0){
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
// left去重
while(left < right && nums[left] == nums[left+1]) left++;
// right去重
while(left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
}else if(sum < 0){
left++; // 和太小,左指针右移增大数值
}else{
right--; // 和太大,右指针左移减小数值
}
}
}
return res;
}
}
3. 核心细节(面试高频提问)
if(i>0 && nums[i]==nums[i-1]) continue跳过重复的第一个数,避免生成重复三元组;必须加i>0,防止i=0下标越界;- 找到sum=0后,先while跳过左右全部重复值,再
left++;right--;只移动指针不去重,会出现重复答案; - 提前break优化:排序后nums[i]>0直接退出循环,后续数字更大不可能凑0;
- 哈希解法缺点:需要Set集合整体去重,代码冗余、常数开销大,面试优先排序双指针;
- 数组排序是本题一切去重、双指针的基础,无序数组无法高效去重。
六、33 搜索旋转排序数组
一、题目前提
- 原数组严格升序,无重复数字;
- 在某一点旋转一次,数组分为两段有序子数组;
- 要求:时间复杂度 (O(logn)) → 必须二分查找,不能遍历。 示例:
[4,5,6,7,0,1,2]
二、核心解题思路
普通二分只需要对比 nums[mid] 和 target;旋转数组数组局部有序,二分新增判断:先判断左 / 右区间哪一段有序
-
取中间下标
mid,若nums[mid]==target直接返回; -
判断左区间
[left,mid]是否有序:
nums[left] <= nums[mid]- 左区间有序:若
target在[nums[left], nums[mid]),收缩右边界right=mid-1;否则去右区间left=mid+1
- 左区间有序:若
-
左区间无序 → 右区间
[mid,right]一定有序
- 右区间有序:若
target在(nums[mid], nums[right]],收缩左边界left=mid+1;否则去左区间right=mid-1
- 右区间有序:若
-
循环终止
left>right,代表不存在目标,返回-1
三、完整标准 Java 代码
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
// 找到目标,直接返回
if(nums[mid] == target){
return mid;
}
// 1. 左半区间有序
if(nums[left] <= nums[mid]){
// target落在左有序区间内
if(target >= nums[left] && target < nums[mid]){
right = mid - 1;
}else{
// target去右边无序段
left = mid + 1;
}
}else{
// 2. 右半区间有序
if(target > nums[mid] && target <= nums[right]){
left = mid + 1;
}else{
// target去左边无序段
right = mid - 1;
}
}
}
// 数组遍历完未找到
return -1;
}
}
四、边界与易错点总结
1. 循环条件
必须 left <= right,只剩一个元素时仍要判断,否则会漏掉答案。
2. mid 防溢出写法
mid = left + (right-left)/2,替代 (left+right)/2,避免大数相加溢出。
3. 有序区间判断 nums[left] <= nums[mid]
- 等于情况:区间只剩一个元素,也算有序;
- 不能用
<,否则长度为 1 的区间会判定无序,逻辑出错。
4. target 区间开闭
- 左有序:
target >= nums[left] && target < nums[mid]mid 位置已经判断过不等于 target,故右边界开区间 - 右有序:
target > nums[mid] && target <= nums[right]mid 已排除,左边界开区间
5. 和普通升序二分的核心区别
- 普通有序:只比较
nums[mid]和 target,直接收缩区间; - 旋转数组:必须先判定哪一段有序,再判断 target 是否落在有序区间内;
- 你之前写的错误代码:缺少「判断右区间有序」分支,只判断左区间,覆盖不全导致查找失败。
五、复杂度分析
- 时间复杂度:(O(logn)),每次二分区间折半;
- 空间复杂度:(O(1)),仅常数变量,原地二分。
六、题型分类与模板总览(做题直接套)
模板1:哈希表快速查找(两数之和)
适用:已知数值,需要快速反向查找下标,无序数组 核心:map.containsKey(目标差值),先查后存,空间换时间
模板2:同向快慢双指针(26、283)
适用:有序/无序数组、原地筛选有效元素、不新开数组 核心:fast遍历筛选,slow维护有效区间末尾,向前覆盖
模板3:左右对撞双指针(11、15内层)
适用:有序数组,求两数组合、面积、和目标 核心:左右两端向中间收缩,根据当前和/高度决定移动哪边指针
模板4:排序+外层循环+内层双指针(三数之和)
适用:三数/四数求和,需要去重、枚举第一个数,剩余两数双指针匹配
七、数组 vs 哈希表 选用总结
- 需要快速判断某个值是否存在、反向查下标 → 哈希表HashMap
- 需要原地修改、有序遍历、区间收缩、双指针 → 纯数组操作
- 三数之和哈希版仅拓展思路,最优解一定是数组排序+双指针