【前端面经】数组算法题解

题目一：两数之和

描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能重复出现。

示例：

输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释：因为 nums[0] + nums[1] = 2 + 7 = 9

技巧和思路：

• 哈希表：使用哈希表来存储数组中的元素及其下标。遍历数组时，每次检查当前元素是否存在于哈希表中。如果存在，则找到了一组和为目标值的元素；如果不存在，则将当前元素和下标存入哈希表。

代码实现：

function twoSum(nums, target) {let map = new Map();for (let i = 0; i < nums.length; i++) {let complement = target - nums[i];if (map.has(complement)) {return [map.get(complement), i];}map.set(nums[i], i);}return [];
}

在这段代码中：

1. map 是一个 JavaScript Map 对象，用于存储数组元素及其下标。
2. 循环遍历数组 nums。
3. 对于每个元素 nums[i]，计算 complement = target - nums[i]，即当前元素需要搭配的另一个数。
4. 检查 map 中是否存在这个 complement。如果存在，说明找到了两个数，它们的和等于 target。
5. map.get(complement) 返回 complement 在数组中的下标，i 是当前元素的下标。所以 return [map.get(complement), i]; 返回的是这两个数的下标。

示例解释：
假设输入 nums = [2, 7, 11, 15]，target = 9。

• 初始化一个空的 Map。
• 第一次循环：i = 0，nums[0] = 2，计算 complement = 9 - 2 = 7，map 中没有 7，所以将 2 存入 map，变为 map = {2: 0}。
• 第二次循环：i = 1，nums[1] = 7，计算 complement = 9 - 7 = 2，map 中有 2，其下标为 0。所以返回 [map.get(2), 1]，即 [0, 1]。

返回的 [0, 1] 表示数组 nums 中下标为 0 和 1 的两个元素（即 2 和 7），它们的和等于目标值 9。

题目二：最长无重复字符子串

描述：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例：

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

技巧和思路：

• 滑动窗口：使用两个指针来表示字符串的当前窗口。右指针不断向右移动，扩展窗口，如果遇到重复字符，则移动左指针，缩小窗口。用一个集合来记录窗口中的字符，保持窗口内字符不重复。

代码实现：

function lengthOfLongestSubstring(s) {let set = new Set();let left = 0, right = 0;let maxLength = 0;while (right < s.length) {if (!set.has(s[right])) {set.add(s[right]);maxLength = Math.max(maxLength, right - left + 1);right++;} else {set.delete(s[left]);left++;}}return maxLength;
}

题目三：合并两个有序数组

描述：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。假定 nums1 有足够的空间来保存 nums2 中的元素。

示例：

输入：
nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3
输出：[1, 2, 2, 3, 5, 6]

技巧和思路：

• 双指针从后向前：因为 nums1 有足够的空间，可以从两个数组的末尾开始比较，将较大的元素放到 nums1 的末尾。这种方法避免了在数组中频繁插入元素，优化了时间复杂度。

代码实现：

function merge(nums1, m, nums2, n) {let i = m - 1, j = n - 1, k = m + n - 1;while (i >= 0 && j >= 0) {if (nums1[i] > nums2[j]) {nums1[k--] = nums1[i--];} else {nums1[k--] = nums2[j--];}}while (j >= 0) {nums1[k--] = nums2[j--];}
}

题目四：寻找数组中的峰值

描述：峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值的索引即可。

示例：

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

技巧和思路：

• 二分查找：利用二分查找的思想，通过比较中间元素与其左右相邻元素的大小，缩小查找范围。

代码实现：

function findPeakElement(nums) {let left = 0, right = nums.length - 1;while (left < right) {let mid = Math.floor((left + right) / 2);if (nums[mid] > nums[mid + 1]) {right = mid;} else {left = mid + 1;}}return left;
}