【基础篇 - Day 19】 2023-03-03 - 1. 两数之和 （04. 哈希表）

[threedayAAAAA]

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

 

示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2：

输入：nums = [3,2,4], target = 6 输出：[1,2] 示例 3：

输入：nums = [3,3], target = 6 输出：[0,1]  

提示：

2 <= nums.length <= 104 -109 <= nums[i] <= 109 -109 <= target <= 109 只会存在一个有效答案  

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路

利用hash表取值复杂度为1的特定， 每次都将当前值存入表中，然后将taget-当前值即为需要找的值，如果在表中存在直接返回即可

代码

function twoSum(nums: number[], target: number): number[] {
    const dataMap = new Map<number, number>()
    for(let i = 0; i < nums.length; i++){
        const mapTarget = target - nums[i]
        if(dataMap.has(mapTarget)){
            return [dataMap.get(mapTarget), i]
        }
        dataMap.set(nums[i], i)
    }
    return []
};

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度: O(N)

[MiumMi]

思路

1. 遍历nums，记录target - 当前元素的剩余值为key值，当前元素的index为value值塞入哈希表

2. 当当前元素已经存在在哈希表中的时候，说明已经找到了相加为target的两个数，取出对应的index组成结果，退出循环并返回

   代码

   function twoSum(nums: number[], target: number): number[] {
   const totalMap = new Map<number, number>();
   let result = [];
   for (let i = 0; i < nums.length; i++) {
       const item = nums[i];
       if (totalMap.has(item)) {
           result = [totalMap.get(item), i];
           break;
       }
       const remain =  target - item;
       if (!totalMap.has(remain)) {
           totalMap.set(remain, i);
       }
   }
   return result;
   };

   ---

   分析

   时间复杂度： O(n) 空间复杂度：O(n)

[yunliuyan]

思路

• 哈希表，将数组的的元素全部存到哈希表中，然后遍历数组，
• target-减去当前元素，若在哈希表中，则返回当前元素和哈希表的值

  代码

  function twoSum(nums: number[], target: number): number[] {
  const hashMap: Map<number, number> = new Map();
  for(let i = 0; i < nums.length; i++) {
      const needNum = target - nums[i];
      if (hashMap.has(needNum)) {
          return [hashMap.get(needNum), i];
      }
      hashMap.set(nums[i], i);
  }
  return [];
  };

  复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)