什么时候想到用哈希法,当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法!!顺便再次回顾一下二分搜索和双指针,二分搜索通常用于已经安好顺序的数组,并且并且不能重复出现,其时间复杂度为 nlogn,双指针主要用于去找到指定的符合条件的subarray。
242.有效的字母异位词.
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
#1 自己看到题目的第一想法
简单的anagram题目,用hash map即可。
#2 看完代码随想录之后的想法
题目basically就是看t是不是出现了s中的所有的characters。经典的hash table的使用场景。
#3 类似题目
383和242是几乎完全一样的题目,为了练习,此题使用了map,而242使用了object。
49比较简单,438其实是之前的双指针做过的题目,是双指针和hashmap的结合。
349. 两个数组的交集
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
#1 自己看到题目的第一想法
两个set即可解决。
顺便复习一下语法,set用has来看是否出现过某值,string中是否出现过某个substring用includes()。
202. 快乐数
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
#1 自己看到题目的第一想法
就使用while循环,直到结果等于1或者是结果已经出现过了(set.size不变) 。
#2 看完代码随想录之后的想法
关于求一个数字的个个位数的和:
const getSum=(num)=>{
let sum=0
while(n) {
sum+=(n%10)
n=Math.floor(n/10)
}
return sum }
#3 收获
对set的操作更加熟悉,set.add(), set.has(), set.size
1. 两数之和
Given an array of integers numsand an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
#1 自己看到题目的第一想法
快速判断是否有某值(target - arr[i]) 出现,就可以考虑用哈希了,
#2 看完代码随想录之后的想法
为什么会想到用哈希表:#1中解释过了
哈希表为什么用map: 因为需要key和value(用来记录下标)
本题map是用来存什么的: target - arr[i]
map中的key和value用来存什么的:value存 arr[i] 的下标
#3 收获
使用数组和set来做哈希法的局限。
数组的大小是受限制的,而且如果元素很少,而哈希值太大会造成内存空间的浪费。
set是一个集合,里面放的元素只能是一个key,而两数之和这道题目,不仅要判断y是否存在而且还要记录y的下标位置,因为要返回x 和 y的下标。所以set 也不能用。
此时就要选择另一种数据结构:map ,map是一种key value的存储结构,可以用key保存数值,用value在保存数值所在的下标。