1.两数之和

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
// 暴力解法,时间复杂度O(n^2)
// var twoSum = function (nums, target) {
//     for (var i = 0; i < nums.length; i++) {
//         for (var j = i + 1; j < nums.length; j++) {
//             if (nums[i] + nums[j] === target) {
//                 return [i, j]
//             }
//         }
//     }
// };

// 使用哈希表,时间复杂度O(n)
var twoSum = function (nums, target) {
    // 维护 target - x 的值
    var map = {}
    for (var i = 0; i < nums.length; i++) {
        if (map[nums[i]] !== undefined) {
            return [map[nums[i]], i]
        }
        map[target - nums[i]] = i
    }
};

// 示例 1：
// 输入：nums = [2,7,11,15], target = 9
// 输出：[0,1]
// 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
console.log(twoSum([2, 7, 11, 15], 9));

// 示例 2：
// 输入：nums = [3,2,4], target = 6
// 输出：[1,2]
console.log(twoSum([3, 2, 4], 6));

// 示例 3：
// 输入：nums = [3,3], target = 6
// 输出：[0,1]
console.log(twoSum([3, 3], 6));