刷题3 剑指 Offer — 哈希表

Map对象的方法：

• set(key, val): 向Map中添加新元素
• get(key): 通过键值查找特定的数值并返回
• has(key): 判断Map对象中是否有Key所对应的值，有返回true,否则返回false
• delete(key): 通过键值从Map中移除对应的数据
• clear(): 将这个Map中的所有元素删除

遍历方法：

• keys()：返回键名的遍历器
• values()：返回键值的遍历器
• entries()：返回键值对的遍历器
• forEach()：使用回调函数遍历每个成员

Set实例对象的方法

• add(value)：添加某个值，返回 Set 结构本身(可以链式调用)。
• delete(value)：删除某个值，删除成功返回true，否则返回false。
• has(value)：返回一个布尔值，表示该值是否为Set的成员。
• clear()：清除所有成员，没有返回值。

遍历方法：

• keys()：返回键名的遍历器
• values()：返回键值的遍历器
• entries()：返回键值对的遍历器
• forEach()：使用回调函数遍历每个成员

剑指 Offer 03. 数组中重复的数字

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzktv1/

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

• 思路 1 使用库函数申请额外空间
  使用 HashSet 来进行处理，因为 HashSet 本身不允许出现重复元素，所以当添加元素失败或已经包含该数字时，则表示出现了重复元素，将其返回即可。
  时间复杂度：O(n)，空间复杂度：O(n)

var findRepeatNumber = function(nums) {
    var numsSet = new Set();
    for(var num of nums){
        if(numsSet.has(num)){
            return num;
        }else{
            numsSet.add(num)
        }
    }
    return false
};

• 思路 2 数组本身做哈希表，达到了节省空间的目的
  时间复杂度：O(n)，空间复杂度：O(1)

var findRepeatNumber = function(nums) {
    for(var i = 0; i<nums.length ; i++){
        while(nums[i] != i){
            if(nums[i] == nums[nums[i]]){
                return nums[i]
            } 
            var tmp = nums[i];
            nums[i] =nums[tmp];
            nums[tmp] = tmp;
        }
    }
    return false
};

剑指 Offer 50. 第一个只出现一次的字符

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzzd25/

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例: s = "abaccdeff" ，返回 "b"；
示例: s = "" ， 返回 " "

• 思路: 首先遍历字符串将每个字符串映射到固定的位置，并且该位置存储字符串的出现次数，然后再遍历一次字符串，找到第一个只出现一次的字符
  时间复杂度：O(n)，空间复杂度：O(1)

var firstUniqChar = function(s) {
    var maps = new Map();
    for(var num of s){
        maps.set(num, maps.has(num))
    }
     for(var num of s){
         if(maps.get(num)==0){
             return num;
         }
     }
    return " "
};