题解 | #两数之和#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param numbers int整型一维数组 
 * @param target int整型 
 * @return int整型一维数组
 */

/**
 * 解法一：双层循环（不可用，运行超时）
 * 思路：详情看以下代码
 * 时间复杂度：O(n^2)，双层循环
 * 空间复杂度：O(1)
 * 注意：如果这里的 nums 是有序的话，优化嵌套循环，可以考虑 “双指针”
 */
// export function twoSum(numbers: number[], target: number): number[] {
//     const res: number[] = []
//     const len = numbers.length
//     if (len === 0) return res

//     for (let i = 0; i < len - 1; i++) {
//         const n1 = numbers[i]
//         let flag = false // 是否得到结果

//         for (let j = i + 1; j < len; j++) {    
//             const n2 = numbers[j]
//             if (n1 + n2 === target) {
//                 res.push(i + 1)
//                 res.push(j + 1)
//                 flag = true
//                 break
//             }
//         }

//         if (flag) break
//     }

//     return res
// }

/**
 * 解法二：哈希
 * 思路：遍历的同时借助哈希表，记录值和下标
 * 时间复杂度：O(n)，最多遍历数组一遍，每次查询哈希表都是O(1)
 * 空间复杂度：O(n)，最坏情况下找到数组结尾才找到，其他都加入哈希表，哈希表最长 n - 1
 */
export function twoSum(numbers: number[], target: number): number[] {
    const res: number[] = []
    const len = numbers.length
    if (len === 0) return res

    const map = new Map()

    for (let i = 0; i < len; i++) {
        const temp = target - numbers[i]
        if (!map.has(temp)) {
            map.set(numbers[i], i)
        } else {
            res.push(map.get(temp) + 1)
            res.push(i + 1)
            return res
        }
    }

    return res
};

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview