数组算法题解题思路与代码分析
1. 双指针
核心解题思路
双指针的核心是通过两个变量（指针）在数组上移动来协同完成任务，从而将多层循环降为一层。主要分两种：
- 相向双指针：左右指针从两端向中间移动，常用于有序数组的查找（如两数之和）或回文串验证。
- 同向双指针（快慢指针）：两指针从同一端出发，移动速度不同，常用于原地修改（如删除重复项）或链表环检测。
经典例题：167. 两数之和 II - 输入有序数组
- 题目：在有序数组中找出两个数，使它们的和为 target。
- 解题思路：利用数组已排序的特性。初始化左指针
left指向开头，右指针right指向结尾。计算nums[left] + nums[right]的和s。如果s等于 target，找到了答案；如果s小于 target，说明和太小，需要增大，左指针右移；如果s大于 target，说明和太大，需要减小，右指针左移。 - 代码分析：javascript
/** * @param {number[]} numbers * @param {number} target * @return {number[]} */ var twoSum = function(numbers, target) { let left = 0; let right = numbers.length - 1; while (left < right) { const sum = numbers[left] + numbers[right]; if (sum === target) { // 题目要求下标从1开始 return [left + 1, right + 1]; } else if (sum < target) { // 和太小，左指针右移增大和 left++; } else { // 和太大，右指针左移减小和 right--; } } return []; // 理论上不会执行到这里 };
2. 滑动窗口
核心解题思路
滑动窗口常用于解决连续子数组的优化问题，如“最长子串”、“最小子数组”。通过维护一个窗口（由左右指针界定），右指针负责扩大窗口（探索新元素），左指针负责收缩窗口（满足条件时尝试优化）。通常配合哈希表记录窗口内的状态。
经典例题：209. 长度最小的子数组
- 题目：给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
- 解题思路：使用滑动窗口，窗口内元素的和为
sum。右指针不断右移，将新元素加入sum。当sum >= target时，尝试收缩左指针，更新最小长度，并减去左指针元素，直到sum < target为止。 - 代码分析：javascript
/** * @param {number} target * @param {number[]} nums * @return {number} */ var minSubArrayLen = function(target, nums) { let left = 0; let sum = 0; let minLen = Infinity; // 初始化为无穷大 for (let right = 0; right < nums.length; right++) { sum += nums[right]; // 右指针元素加入窗口 // 当窗口和满足条件时，尝试收缩左边界 while (sum >= target) { // 更新最小长度 minLen = Math.min(minLen, right - left + 1); // 左指针右移，从和中移除左指针元素 sum -= nums[left]; left++; } } return minLen === Infinity ? 0 : minLen; };
3. 前缀和 & 哈希表优化
核心解题思路
前缀和能快速计算任意子数组的和：sum(i, j) = preSum[j] - preSum[i-1]。当需要统计满足某种条件的子数组个数时，常结合哈希表存储前缀和出现的次数，从而在一次遍历中完成统计，将时间复杂度从 O(n²) 降到 O(n)。
经典例题：560. 和为 K 的子数组
- 题目：给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的连续子数组的个数。
- 解题思路：遍历数组，计算当前前缀和
currentSum。我们想找的是有多少个i使得currentSum - preSum[i] = k，即preSum[i] = currentSum - k。用哈希表map记录每个前缀和出现的次数。每到一个位置，先查询map中有多少个currentSum - k，累加到结果中，然后将当前前缀和存入map。 - 代码分析：javascript
/** * @param {number[]} nums * @param {number} k * @return {number} */ var subarraySum = function(nums, k) { const map = new Map(); map.set(0, 1); // 前缀和为0的初始出现次数为1（空数组） let count = 0; let currentSum = 0; for (let i = 0; i < nums.length; i++) { currentSum += nums[i]; // 如果存在前缀和为 currentSum - k，说明这些位置到当前位置的子数组和为k if (map.has(currentSum - k)) { count += map.get(currentSum - k); } // 更新当前前缀和的出现次数 map.set(currentSum, (map.get(currentSum) || 0) + 1); } return count; };
4. 二分查找
核心解题思路
二分查找适用于有序数组中查找特定元素或边界。核心是每次将搜索区间缩小一半，时间复杂度 O(log n)。关键点在于循环不变量（区间开闭）和边界条件的处理。
经典例题：34. 在排序数组中查找元素的第一个和最后一个位置
- 题目：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。
- 解题思路：使用两次二分查找，分别寻找左边界（第一个等于 target 的位置）和右边界（最后一个等于 target 的位置）。寻找左边界时，当
nums[mid] >= target时向左收缩；寻找右边界时，当nums[mid] <= target时向右收缩。 - 代码分析：javascript
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var searchRange = function(nums, target) { const binarySearch = (isLeft) => { let left = 0; let right = nums.length - 1; let result = -1; while (left <= right) { const mid = Math.floor((left + right) / 2); if (nums[mid] === target) { result = mid; // 记录当前位置 if (isLeft) { right = mid - 1; // 找左边界，向左收缩 } else { left = mid + 1; // 找右边界，向右收缩 } } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; }; const leftIndex = binarySearch(true); const rightIndex = binarySearch(false); return [leftIndex, rightIndex]; };
5. 贪心算法
核心解题思路
贪心算法在每一步选择中都采取当前状态下最优的选择，从而希望最终结果是全局最优。通常需要证明贪心策略的正确性。适用于一些最值问题，如区间调度、跳跃游戏等。
经典例题：55. 跳跃游戏
- 题目：给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
- 解题思路：维护一个变量
maxReach表示当前能到达的最远位置。遍历数组，如果当前位置i超过了maxReach（即无法到达当前位置），则返回 false。否则更新maxReach为max(maxReach, i + nums[i])。最后判断maxReach是否大于等于最后一个下标。 - 代码分析：javascript
/** * @param {number[]} nums * @return {boolean} */ var canJump = function(nums) { let maxReach = 0; for (let i = 0; i < nums.length; i++) { if (i > maxReach) return false; // 当前不可达 maxReach = Math.max(maxReach, i + nums[i]); if (maxReach >= nums.length - 1) return true; // 提前结束 } return true; };
6. 动态规划
核心解题思路
动态规划用于解决具有重叠子问题和最优子结构的问题。核心步骤：定义 dp 数组的含义，推导状态转移方程，确定初始条件和遍历顺序。
经典例题：53. 最大子数组和
- 题目：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
- 解题思路：定义
dp[i]表示以nums[i]结尾的连续子数组的最大和。状态转移：dp[i] = Math.max(dp[i-1] + nums[i], nums[i])。即要么延续之前的子数组，要么从当前元素重新开始。最终答案是所有dp[i]中的最大值，可以优化为滚动变量。 - 代码分析：javascript
/** * @param {number[]} nums * @return {number} */ var maxSubArray = function(nums) { let prev = nums[0]; // 相当于 dp[i-1] let max = prev; for (let i = 1; i < nums.length; i++) { // 状态转移 prev = Math.max(prev + nums[i], nums[i]); max = Math.max(max, prev); } return max; };
7. 矩阵操作
核心解题思路
矩阵可以看作是二维数组，通常考察坐标变换、模拟遍历和原地修改。常用技巧：方向数组、按层处理、原地标记等。
经典例题：54. 螺旋矩阵
- 题目：给你一个 m 行 n 列的矩阵 matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。
- 解题思路：定义上下左右四个边界，按照“从左到右、从上到下、从右到左、从下到上”的顺序遍历，每遍历完一条边就收缩对应的边界，直到边界交错。
- 代码分析：javascript
/** * @param {number[][]} matrix * @return {number[]} */ var spiralOrder = function(matrix) { if (matrix.length === 0) return []; let top = 0; let bottom = matrix.length - 1; let left = 0; let right = matrix[0].length - 1; const result = []; while (top <= bottom && left <= right) { // 从左到右遍历上边 for (let j = left; j <= right; j++) { result.push(matrix[top][j]); } top++; // 从上到下遍历右边 for (let i = top; i <= bottom; i++) { result.push(matrix[i][right]); } right--; // 如果还有下边（防止重复） if (top <= bottom) { // 从右到左遍历下边 for (let j = right; j >= left; j--) { result.push(matrix[bottom][j]); } bottom--; } // 如果还有左边 if (left <= right) { // 从下到上遍历左边 for (let i = bottom; i >= top; i--) { result.push(matrix[i][left]); } left++; } } return result; };
8. 进阶技巧
核心解题思路
进阶题往往需要综合运用多种技巧，或者借助特殊的数据结构（如单调栈、并查集、堆等）。解题时需要根据题目特点灵活选择。
经典例题：42. 接雨水
- 题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
- 解题思路：可以使用单调栈（维护递减栈）或双指针（左右最大值）来解。这里演示双指针法：每个位置能接的雨水量等于
min(左边最高, 右边最高) - 当前高度。使用左右指针和两个变量leftMax、rightMax来动态更新。 - 代码分析：javascript
/** * @param {number[]} height * @return {number} */ var trap = function(height) { let left = 0; let right = height.length - 1; let leftMax = 0; let rightMax = 0; let result = 0; while (left < right) { if (height[left] < height[right]) { // 左边较矮，leftMax 决定左边可能的积水高度 if (height[left] >= leftMax) { leftMax = height[left]; // 更新左边最大值 } else { result += leftMax - height[left]; // 可以接雨水 } left++; } else { // 右边较矮或相等 if (height[right] >= rightMax) { rightMax = height[right]; } else { result += rightMax - height[right]; } right--; } } return result; };
总结
- 双指针、二分查找：基础技巧，容易上手。
- 滑动窗口、前缀和：经典优化方法，有固定模板。
- 贪心、动态规划：思维要求较高，多练多总结。
- 矩阵操作、进阶技巧：作为综合练习，提升代码能力。