← 返回学习路线

SYSTEM

LeetCode 5道高频数组题 完整总结

LeetCode题解
src/content/notes/algorithm/数组双指针.md

LeetCode 5道高频数组题 完整总结

包含:两数之和、26删除有序数组重复项、283移动零、11盛最多水容器、15三数之和 分三块:核心思路、标准代码、必踩细节,秋招笔试面试直接背诵

一、1. 两数之和

1. 核心思路

数组短板:只知道数值找下标需要遍历O(n) 用哈希表空间换时间,一次遍历完成:

  1. 遍历当前数 nums[i],计算目标配对值 need = target - nums[i]
  2. 查表:如果存在need,直接返回 [map.get(need), i]
  3. 不存在就把 (当前值,下标) 存入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. 关键细节(踩坑点)

  1. 先判断containsKey,后put 如果先存再判断,会取到当前自身,出现 [i,i] 重复下标错误;
  2. HashMap存key=数值,value=下标,因为我们需要通过值反向查位置;
  3. 题目保证唯一解,循环内一定return,末尾空数组仅语法补齐。

二、26. 删除有序数组中的重复项

1. 核心思路:同向快慢双指针(原地覆盖)

有序数组重复元素相邻,原地修改不能新开数组:

  • slow慢指针:维护无重复有效区间末尾
  • fast快指针:遍历全数组,筛选不重复的新元素
  1. fast找到和slow不相等的数字,slow先前进一位
  2. 将fast的值覆盖到slow位置
  3. 最终有效长度 = 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. 关键细节

  1. 边界:数组为空直接返回0;
  2. slow初始0,fast从1开始,对比相邻元素;
  3. 只覆盖前slow+1位,后面剩余数字题目忽略不用清理;
  4. 模板通用:筛选有效元素向前覆盖,和283移动零是一套模板。

三、283. 移动零

1. 核心思路:同向快慢双指针(原地分离有效值)

要求:原地操作、非零数字相对顺序不变

  • slow:记录下一个非0该存放的位置
  • fast:遍历筛选所有非0数字
  1. fast遇到非0,覆盖到slow位置,slow++
  2. 一轮遍历后 [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. 关键细节

  1. 不能新建数组存储非0,违反原地操作要求;
  2. 必须先移非0再补0,保证原有数字相对顺序不乱;
  3. 和26题模板统一:fast筛选有效元素,slow维护有效区间;
  4. 不能用左右对撞双指针:会打乱非零元素原有顺序。

四、11. 盛最多水的容器

1. 核心思路:左右对撞双指针(压缩宽度求最大面积)

面积公式:宽 × 矮边高度

  1. left在最左,right在最右,初始宽度最大
  2. 计算当前面积,更新最大值
  3. 移动高度更小的一侧指针:只有移动矮边,才有可能提升高度、得到更大面积;移动高边只会宽度变小,面积必然更小
  4. 两指针相遇结束遍历
  • 时间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. 关键细节

  1. 面积由较短柱子决定,高柱子再高也留不住水;
  2. 指针移动规则:谁矮移谁,是本题最优解核心;
  3. 暴力两层循环枚举所有左右组合O(n²),大数据直接超时;
  4. 对比同向双指针:本题是左右收缩对撞,前两题是从前到后同向遍历。

五、15. 三数之和(最优:排序+同向双指针)

1. 核心思路

  1. 先排序数组,让重复数字相邻,方便去重;
  2. 外层循环固定第一个数nums[i],目标转化为:在i右侧区间找两数之和 = -nums[i];
  3. i右侧用左右对撞双指针找两数,和为0记录答案;
  4. 三层去重保证结果无重复三元组:
    • 外层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. 核心细节(面试高频提问)

  1. if(i>0 && nums[i]==nums[i-1]) continue 跳过重复的第一个数,避免生成重复三元组;必须加i>0,防止i=0下标越界;
  2. 找到sum=0后,先while跳过左右全部重复值,再left++;right--;只移动指针不去重,会出现重复答案;
  3. 提前break优化:排序后nums[i]>0直接退出循环,后续数字更大不可能凑0;
  4. 哈希解法缺点:需要Set集合整体去重,代码冗余、常数开销大,面试优先排序双指针;
  5. 数组排序是本题一切去重、双指针的基础,无序数组无法高效去重。

六、33 搜索旋转排序数组

一、题目前提

  1. 原数组严格升序,无重复数字;
  2. 在某一点旋转一次,数组分为两段有序子数组;
  3. 要求:时间复杂度 (O(logn)) → 必须二分查找,不能遍历。 示例:[4,5,6,7,0,1,2]

二、核心解题思路

普通二分只需要对比 nums[mid] 和 target;旋转数组数组局部有序,二分新增判断:先判断左 / 右区间哪一段有序

  1. 取中间下标 mid,若 nums[mid]==target 直接返回;

  2. 判断左区间

    [left,mid]

    是否有序:

    nums[left] <= nums[mid]
    • 左区间有序:若 target 在 [nums[left], nums[mid]),收缩右边界 right=mid-1;否则去右区间 left=mid+1
  3. 左区间无序 → 右区间

    [mid,right]

    一定有序

    • 右区间有序:若 target 在 (nums[mid], nums[right]],收缩左边界 left=mid+1;否则去左区间 right=mid-1
  4. 循环终止 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 是否落在有序区间内;
  • 你之前写的错误代码:缺少「判断右区间有序」分支,只判断左区间,覆盖不全导致查找失败。

五、复杂度分析

  1. 时间复杂度:(O(logn)),每次二分区间折半;
  2. 空间复杂度:(O(1)),仅常数变量,原地二分。

六、题型分类与模板总览(做题直接套)

模板1:哈希表快速查找(两数之和)

适用:已知数值,需要快速反向查找下标,无序数组 核心:map.containsKey(目标差值),先查后存,空间换时间

模板2:同向快慢双指针(26、283)

适用:有序/无序数组、原地筛选有效元素、不新开数组 核心:fast遍历筛选,slow维护有效区间末尾,向前覆盖

模板3:左右对撞双指针(11、15内层)

适用:有序数组,求两数组合、面积、和目标 核心:左右两端向中间收缩,根据当前和/高度决定移动哪边指针

模板4:排序+外层循环+内层双指针(三数之和)

适用:三数/四数求和,需要去重、枚举第一个数,剩余两数双指针匹配

七、数组 vs 哈希表 选用总结

  1. 需要快速判断某个值是否存在、反向查下标 → 哈希表HashMap
  2. 需要原地修改、有序遍历、区间收缩、双指针 → 纯数组操作
  3. 三数之和哈希版仅拓展思路,最优解一定是数组排序+双指针