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

题目一：两数之和

描述：给定一个整数数组 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;
}