目录
- 242.有效的字母异位符
- 方法一:使用两个map对象来保存
- 方法二:使用一个map
- 349.两个数组的交集
- 方法一:set+map+for of
- 方法二:只是用set
242.有效的字母异位符
方法一:使用两个map对象来保存
时间复杂度:O(n) 空间复杂度O(n)
var isAnagram = function(s, t) {if(s.length!==t.length) return false //如果长度不等,那么一定不满足要求//分别对字符串s t进行遍历,然后分别使用map对象进行保存let map1 = new Map()let map2 = new Map()//字符串是可迭代的,可以使用for of进行遍历for(let item of s){map1.set(item,map1.get(item)+1||1)}for(let item of t){map2.set(item,map2.get(item)+1||1)}//第三个循环 使用for of从map1中拿key,然后对map2中的进行比较for(let [key,val] of map1){//注意,当map1中的所有的属性所对应的值都和map2中的相等的时候,不存在map2中比map1多一个属性的情况if(!map2.get(key)||map2.get(key)!==val){return false}}return true
};
方法二:使用一个map
var isAnagram = function(s, t) {//使用一个map对象let map = new Map()for(let val of s){map.set(val,map.get(val)+1||1)}//然后遍历t,从map中进行相减for(let key of t){//map中没有这个键if(!map.has(key)) return falsemap.set(key,map.get(key)-1)if(map.get(key)==0) map.delete(key)}if(map.size==0) return truereturn false
};
349.两个数组的交集
方法一:set+map+for of
var intersection = function(nums1, nums2) {//时空复杂度都是O(n)//使用一个map对象来保存num1中的每一个键,然后使用arr保存两者间的相同的let map = new Map()let arr = []for(let val of nums1){map.set(val,map.get(val)+1||1)}for(let val of nums2){if(map.has(val)){arr.push(val)}}//set进行去重,然后再将对象转换为数组return Array.from(new Set(arr))
};
方法二:只是用set
时空都是O(n)
new Set()毫无疑问是O(n)
Array.from()也是O(n),原因见第三条:
var intersection = function(nums1, nums2) {let a = new Set(nums1)let b = new Set(nums2)return [...a].filter(item =>b.has(item))
};