leetcode-数组-1-两数之和

1. 两数之和

描述

• 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

示例 1

    给定 nums = [2, 7, 11, 15], target = 9

    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

思路 1

• 暴力法

详解 1

• 1.遍历每个元素 x
• 2.并查找是否存在一个值与 target - x 相等的目标元素。

解法 1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function (nums, target) {
      for(let i =0 ;i<nums.length;i++){
          for(let j = i+1;j<nums.length;j++){
              if(nums[i] + nums[j] === target){
                  return [i,j]
              }
          }
      }
};

复杂度分析 1

• 时间复杂度： O( n^2 )
• 空间复杂度：O(1)

思路 2

• 利用Map

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function (nums, target) {
     let mapObj = new Map()
     for(let i =0;i<nums.length;i++){
         let res = target - nums[i];
         if(mapObj.has(res)){
             return [mapObj.get(res),i]
         }else{
             map.set(nums[i],i)
         }
     }
};

复杂度

• 时间复杂度：O(n)。只遍历了包含有 n 个元素的列表一次
• 空间复杂度：O(n)。上述解法中，申请了大小为 的空间，空间复杂度跟数字的个数 n 线性相关