前端常见算法题(数组篇)--上
2026-05-10 23:38:37
前端常见数组算法题及解法总结
一、两数之和问题描述：给定整数数组 nums 和目标值 target，返回两个数之和等于 target 的索引，且同一元素不可重复使用。
解法对比：
方案一（暴力法）
思路：双层循环遍历所有可能组合，检查和是否等于 target。
复杂度：时间复杂度 O(n2)，空间复杂度 O(1)。
缺点：效率低，不适合大规模数据。
方案二（栈优化）
思路：利用 pop 和 indexOf 模拟栈操作，减少内层循环次数。
复杂度：时间复杂度 O(n2)（pop 和 indexOf 仍需遍历），空间复杂度 O(1)。
缺点：pop 会修改原数组，且 indexOf 效率不高。
方案三（哈希表）
思路：遍历数组时，用哈希表存储已访问元素及其索引，检查 target - nums[i] 是否存在。
复杂度：时间复杂度 O(n)，空间复杂度 O(n)。
推荐：最优解，适合大规模数据。
代码示例（方案三）：
var twoSum = function(nums, target) { const map = new Map(); for (let i = 0; i < nums.length; i++) { const otherIndex = map.get(target - nums[i]); if (otherIndex !== undefined) return [otherIndex, i]; map.set(nums[i], i); }};二、三数之和问题描述：找出数组中所有不重复的三元组 [a, b, c]，使得 a + b + c = 0。
解法对比：
方案一（双指针法）
思路：
排序数组，固定第一个数 nums[i]。
使用双指针 left 和 right 在剩余部分寻找 nums[left] + nums[right] = -nums[i]。
跳过重复元素以避免重复解。
复杂度：时间复杂度 O(n2)，空间复杂度 O(1)（排序可能为 O(log n)）。
推荐：高效且易于实现。
方案二（哈希表法）
思路：固定第一个数 nums[i]，将问题转化为两数之和，用哈希表存储剩余部分。
复杂度：时间复杂度 O(n2)，空间复杂度 O(n)。
缺点：去重逻辑复杂，容易遗漏或重复解。
代码示例（方案一）：
var threeSum = function(nums) { nums.sort((a, b) => a - b); const r = []; for (let i = 0; i < nums.length; i++) { if (i > 0 && nums[i] === nums[i - 1]) continue; let left = i + 1, right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { r.push([nums[i], nums[left], nums[right]]); while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } else if (sum < 0) left++; else right--; } } return r;};三、最接近的三数之和问题描述：找出三个数的和与 target 最接近的值。
解法：
- 思路：
排序数组，固定第一个数 nums[i]。
使用双指针 left 和 right 在剩余部分寻找最接近 target - nums[i] 的和。
更新最接近的和 r，并移动指针。
- 复杂度：时间复杂度 O(n2)，空间复杂度 O(1)。
代码示例：
var threeSumClosest = function(nums, target) { nums.sort((a, b) => a - b); let r = nums[0] + nums[1] + nums[2]; for (let i = 0; i < nums.length - 2; i++) { let left = i + 1, right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (Math.abs(sum - target) < Math.abs(r - target)) r = sum; if (sum === target) return sum; else if (sum < target) left++; else right--; } } return r;};四、四数之和问题描述：找出所有不重复的四元组 [a, b, c, d]，使得 a + b + c + d = target。
解法：
- 思路：
排序数组，固定前两个数 nums[i] 和 nums[j]。
将问题转化为两数之和，用双指针在剩余部分寻找 nums[left] + nums[right] = target - nums[i] - nums[j]。
跳过重复元素以避免重复解。
- 复杂度：时间复杂度 O(n3)，空间复杂度 O(1)（排序可能为 O(log n)）。
代码示例：
var fourSum = function(nums, target) { nums.sort((a, b) => a - b); const r = []; for (let i = 0; i < nums.length - 3; i++) { if (i > 0 && nums[i] === nums[i - 1]) continue; for (let j = i + 1; j < nums.length - 2; j++) { if (j > i + 1 && nums[j] === nums[j - 1]) continue; let left = j + 1, right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum === target) { r.push([nums[i], nums[j], nums[left], nums[right]]); while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } else if (sum < target) left++; else right--; } } } return r;};总结- 两数之和：优先使用哈希表法（O(n)）。
- 三数/四数之和：排序后用双指针法（O(n2) / O(n3)），注意去重逻辑。
- 最接近三数之和：双指针法，动态更新最接近值。
- 核心技巧：排序 + 双指针 + 哈希表，适用于多数数组求和问题。
热门标签
