你好我是fengxin_rou这是我的个人主页fengxin_rou的主页❄️欢迎查看我的专栏我的专栏《Java后端学习》、《JAVASE基础》、《JUC并发》、《redis》、《JVM虚拟机》、《MYSQL》、《黑马点评》、《rabbitmq》、《JavaWebAI的talis学习系统》、《苍穹外卖》目录引言一、LeetCode53 最大子数组和1.1 题目释义1.2 前缀和解题原理1.3 原始代码逐行拆解1.4 空间优化版前缀和实现1.5 Kadane 动态规划最优解法1.6 复杂度汇总1.7 边界自测用例二、LeetCode189 轮转数组2.1 题目释义2.2 辅助数组解题原理2.3 原始代码逐行拆解2.4 原地三次反转最优解法2.5 复杂度汇总2.6 边界自测用例三、LeetCode56 合并区间3.1 题目释义3.2 贪心 排序解题原理3.3 原始代码逐行拆解3.4 边界场景分类测试3.5 复杂度分析四、三道题目整体考点总结与拓展4.1 各题核心考点梳理4.2 同类题目拓展方向4.3 刷题落地建议结语引言数组是算法笔试、技术面试中出现频次最高的题型之一LeetCode53、189、56 三道题目分属前缀和、数组下标运算、贪心 排序三类经典模型覆盖数组模块三大核心解题思想。三道题目难度均为中等是入门贪心、前缀和、原地数组操作的标杆例题。本文从题意、解题原理、原始代码逐行剖析、代码优化、复杂度分析、边界测试多个维度客观拆解每道题目所有解法基于 Java 语言实现兼顾可读性与工程落地性。一、LeetCode53 最大子数组和1.1 题目释义给定整型数组 nums查找数组中一段元素连续的子数组要求子数组内所有元素累加和为全局最大值子数组不可为空最终返回该最大累加数值。 示例 1输入[-2,1,-3,4,-1,2,1,-5,4]最优连续子数组[4,-1,2,1]结果为 6 示例 2输入单元素数组[1]直接返回 1 示例 3全正数数组[5,4,-1,7,8]整体作为子数组结果 23。题目隐含边界数组元素可全为负数、正负混合、全正数解题逻辑需要兼容全部场景。1.2 前缀和解题原理前缀和是连续区间求和的通用工具定义前缀和数组 preCountpreCount[0]0preCount[i]代表原数组前 i 个元素累加结果计算公式 \(preCount[i]preCount[i-1]nums[i-1]\) 连续子数组nums[l~r]区间和推导公式\(sumpreCount[r1]-preCount[l]\)。 想要让区间和尽可能大在固定右侧下标r1时只需要保证左侧前缀和preCount[l]是preCount[0]~preCount[r]中的最小值。 解题拆分三步预处理完整前缀和数组遍历前缀和动态记录遍历路径中出现过的最小前缀和 minPre每一轮使用当前前缀和减去历史最小前缀和更新全局最大子数组和 maxSum。运算顺序硬性约束先用历史最小前缀和计算区间和→更新最大值→再刷新最小前缀和若顺序颠倒会出现当前前缀和自减、区间选取长度为 0 的错误。1.3 原始代码逐行拆解class Solution { public int maxSubArray(int[] nums) { int len nums.length; int[] preCount new int[len 1]; preCount[0] 0; int minPre preCount[0]; int maxSum Integer.MIN_VALUE; // 生成前缀和数组 for(int i 0; i len; i){ preCount[i 1] preCount[i] nums[i]; } // 遍历前缀和求最大区间 for (int i 1; i len; i) { int temp preCount[i] - minPre; maxSum Math.max(maxSum, temp); minPre Math.min(minPre, preCount[i]); } return maxSum; } }preCount数组长度开辟为len1preCount[0]0是空区间前缀和规避从下标 1 开始无法截取数组首段区间的问题maxSum初始赋值为Integer.MIN_VALUE专门适配数组全为负数场景保证最小负数可以被正常收录首轮循环批量算出全部前缀和数据第二轮循环完成极值统计。1.4 空间优化版前缀和实现原始写法开辟 O (n) 长度前缀和数组空间开销偏高。优化思路不存储完整前缀和数组用单个变量实时累加更新当前前缀和 currentPre空间复杂度压缩至 O (1)代码如下class Solution { public int maxSubArray(int[] nums) { int minPre 0; int currentPre 0; int maxSum Integer.MIN_VALUE; for (int num : nums) { currentPre num; maxSum Math.max(maxSum, currentPre - minPre); minPre Math.min(minPre, currentPre); } return maxSum; } }优化前后时间复杂度不变仍为 O (n)仅优化空间维度。1.5 Kadane 动态规划最优解法除前缀和外本题行业通用最优写法为 Kadane 动态规划算法核心状态定义dp 代表以当前遍历元素作为区间结尾的最大连续子数组和。 状态转移对于当前元素 num要么单独开启新子数组num要么拼接在前一个子数组后方dpnum即\(dpmax(num,dpnum)\)。遍历全程同步记录 dp 的全局最大值即为答案。class Solution { public int maxSubArray(int[] nums) { int dp nums[0]; int max nums[0]; for(int i1; inums.length; i){ dp Math.max(nums[i], dp nums[i]); max Math.max(max, dp); } return max; } }该解法时间 O (n)、空间 O (1)是面试首选写法。1.6 复杂度汇总表格方案时间复杂度空间复杂度适用场景原始前缀和O(n)O(n)初学理解前缀和逻辑优化前缀和O(n)O(1)兼顾前缀和思路与空间Kadane DPO(n)O(1)面试标准作答1.7 边界自测用例全负数组[-3,-1,-2]输出 - 1单元素[9]输出 9正负穿插[2,-1,3]输出 4。二、LeetCode189 轮转数组2.1 题目释义给定非负整数 k 与整型数组 nums数组整体向右轮转 k 个位置要求最终在原数组上完成数值修改。 示例 1nums[1,2,3,4,5,6,7],k3轮转结果[5,6,7,1,2,3,4] 示例 2nums[-1,-100,3,99],k2轮转结果[3,99,-1,-100]。 关键隐藏条件k 可以大于数组长度数组长度 n轮转 n 次等价于数组无变化。2.2 辅助数组解题原理向右轮转下标映射规则原数组下标 i 对应的元素轮转后新下标为\((ik)\%n\)。 取模运算核心作用消除 k 大于数组长度的无效轮转次数。例如 n7k10\(10\%73\)等价于只向右轮转 3 次。 解题步骤开辟等长辅助数组 result根据下标映射公式把原数组元素存入辅助数组对应位置将辅助数组全部数据覆盖写入原数组满足原地修改要求。2.3 原始代码逐行拆解class Solution { public void rotate(int[] nums, int k) { int len nums.length; int[] result new int[len]; for(int i 0 ; i len ; i){ result[ (i k)%len] nums[i]; } for (int i 0; i len; i) { nums[i] result[i]; } } }代码缺陷未对 k 预处理当 k 远大于 len 时取模运算重复计算增加无效开销。优化补充kk%len;if(k0)return;k 等于 0 代表无需轮转直接结束方法。 优化后代码java运行class Solution { public void rotate(int[] nums, int k) { int len nums.length; k k % len; if(k 0) return; int[] result new int[len]; for(int i0; ilen; i){ result[(ik)%len] nums[i]; } System.arraycopy(result, 0, nums, 0, len); } }System.arraycopy是底层原生数组复制方法循环赋值替换为该 API 提升执行效率。2.4 原地三次反转最优解法辅助数组方案空间 O (n)行业最优解法采用数组区间反转空间压缩至 O (1)三步固定流程反转整个数组全部元素反转数组前 k 个元素反转剩余 n-k 个元素。 实例演算[1,2,3,4,5,6,7],k3全反转[7,6,5,4,3,2,1]前 3 位反转[5,6,7,4,3,2,1]后 4 位反转[5,6,7,1,2,3,4]。 实现代码class Solution { public void rotate(int[] nums, int k) { int n nums.length; k % n; reverse(nums, 0, n-1); reverse(nums, 0, k-1); reverse(nums, k, n-1); } private void reverse(int[] nums, int left, int right){ while(left right){ int temp nums[left]; nums[left] nums[right]; nums[right] temp; left; right--; } } }reverse 函数实现指定闭区间 [left,right] 元素首尾互换。2.5 复杂度汇总辅助数组方案时间 O (n)空间 O (n)三次反转方案时间 O (n)空间 O (1)。2.6 边界自测用例k0[1,2],k0数组不变k 等于数组长度[1,2,3],k3数组不变kn[1,2],k5\(5\%21\)结果[2,1]。三、LeetCode56 合并区间3.1 题目释义输入二维数组 intervals每个一维数组[start,end]代表一个连续区间区间之间存在重叠、相接、分离三种关系合并所有存在重叠或端点相接的区间最终返回无重叠的新区间数组。 示例 1[[1,3],[2,6],[8,10],[15,18]][1,3] 与 [2,6] 重叠合并输出[[1,6],[8,10],[15,18]] 示例 2[[1,4],[4,5]]端点相接视为重叠合并为[[1,5]]。3.2 贪心 排序解题原理区间合并通用前置操作按照区间左边界升序排序。排序完成后所有能够重叠的区间必然在数组中相邻只需要顺序遍历和结果集合末尾区间做比较即可。 合并判定规则 设结果集合最后一个区间为[lastL,lastR]当前遍历区间[curL,curR]curL lastR两区间重叠 / 相连合并新区间右边界更新\(lastRmax(lastR,curR)\)curL lastR无交集当前区间直接存入结果集合。 选用 ArrayList 存储结果优势是长度动态扩容不用提前预判最终数组长度。3.3 原始代码逐行拆解class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals,(p,q) - p[0] - q[0]); Listint[] result new ArrayList(); for(int[] p : intervals){ int m result.size(); if( m 0 p[0] result.get(m-1)[1]){ result.get(m-1)[1] Math.max(p[1],result.get(m-1)[1]); }else{ result.add(p); } } return result.toArray(new int[result.size()][]); } }Arrays.sort(intervals,(p,q)-p[0]-q[0])利用 lambda 实现二维数组按左端点升序m 为结果集合当前长度m0 代表集合已有数据可以取末尾区间对比result.toArray(new int[result.size()][])是 Java 集合转二维数组固定写法。3.4 边界场景分类测试空输入intervals new int[0][]返回空数组单个区间[[3,7]]直接原数据返回完全包含[[1,10],[2,3],[4,5]]合并为[[1,10]]端点贴合[[2,5],[5,9]]合并[2,9]。3.5 复杂度分析排序是整个算法性能瓶颈排序时间 O (nlogn)单次遍历 O (n)综合时间复杂度 O (nlogn) 空间结果数组必开 O (n)排序栈开销 O (logn)不计输出空间额外空间 O (logn)。四、三道题目整体考点总结与拓展4.1 各题核心考点梳理53 最大子数组和前缀和区间公式、极值动态维护、DP 状态拆分连续子数组求和模板题189 轮转数组数组下标取模映射、原地数组反转、空间复杂度优化思想考察数组下标逻辑56 合并区间自定义排序、贪心区间合并准则、List 与数组互转区间类问题万能模板。4.2 同类题目拓展方向53 衍生LeetCode974 和可被 K 整除的子数组、最长和为 target 的子数组均可以使用前缀和 哈希表求解189 衍生数组左旋转、循环链表位移同样依托取模与区间反转思想56 衍生LeetCode57 插入区间、LeetCode452 用最少弓箭射气球排序 贪心逻辑完全复用。4.3 刷题落地建议三道题为数组算法三大分支入门标杆实操练习建议分三步 第一步默写原始基础写法吃透基础逻辑 第二步自主尝试优化空间复杂度写出 O (1) 空间最优代码 第三步刷对应拓展变式固化解题模板形成条件反射。结语本文从基础实现到优化方案完整覆盖三道高频考题三种解题思想贯穿数组算法体系。前缀和用于连续区间统计、取模用于循环下标映射、排序贪心用于区间整合三类思路可以复用到大量同类型算法题目中熟练掌握后可以覆盖半数中等难度数组面试题。在实际工程开发中前缀和用于预处理大数据区间查询区间合并用于日程、时间片数据整合数组轮转用于环形缓冲区实现算法逻辑与业务落地具备较强关联性。