Leetcode 1 两数之和 （暴力循环 HashMap* ） 含set、数组、map作哈希表的特性分析*

之和 （暴力循环 HashMap* ） 含set、数组、map作哈希表的特性分析*"/>

Leetcode 1 两数之和 （暴力循环 HashMap* ） 含set、数组、map作哈希表的特性分析*

Leetcode 1 两数之和 （暴力循环 + 哈希表）

• • 解法1 ： 暴力循环
  • 解法2 : 哈希表HashMap法
  • • :red_circle:为什么想到用哈希表呢？
    • :red_circle:为什么想到用map呢？
    • :red_circle:归纳使用数组、set、map做哈希法：

题目链接：1. 两数之和

解法1 ： 暴力循环

暴力解法中输出数组：
return new int[]{i, j};
return new int[0]; // 找不到的话就返回一个空的整形数组

时间复杂度O(N^2)
空间复杂度O(1)

class Solution {public int[] twoSum(int[] nums, int target) {int res1 = -1;int res2 = -1;for(int i = 0; i < nums.length-1; i++){for(int j = i+1; j < nums.length; j++){if(nums[i] + nums[j] == target){return new int[]{i,j};}}}return new int[0];  // 找不到的话就返回一个空的整形数组   }
}

解法2 : 哈希表HashMap法

🔴为什么想到用哈希表呢？

✋当需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要想到哈希法。

🔴为什么想到用map呢？

本题，不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。因此使用哈希法

🔴归纳使用数组、set、map做哈希法：

242 有效的字母异位词 (opens new window)是用数组作为哈希表来解决哈希问题
349 两个数组的交集 (opens new window)是通过set作为哈希表来解决哈希问题。

数组：大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合：里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
map :map是一种key - value的存储结构，可以用key保存数值，用value再保存数值所在的下标。

时间复杂度O(N)
空间复杂度O(N)