哈希表理論基礎(chǔ)

什么時(shí)候想到用哈希法，當(dāng)我們遇到了要快速判斷一個(gè)元素是否出現(xiàn)集合里的時(shí)候，就要考慮哈希法。

文章講解：https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

有效的字母異位詞

題目鏈接/文章講解/視頻講解： https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

第一想法

運(yùn)用數(shù)組來做哈希表

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if (s.length !== t.length) return false
    let res = new Array(26).fill(0)
    for(let i of s) {
        res[i.charCodeAt() - "a".charCodeAt()]++
    }
    for(let j of t) {
        res[j.charCodeAt() - "a".charCodeAt()]--
    }
    for(let q = 0 ; q < 26 ; q++){
        if(res[q] !== 0) return false
    }
    return true
};

兩個(gè)數(shù)組的交集

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

第一想法

數(shù)字小的時(shí)候用數(shù)組，數(shù)字大的時(shí)候用set，需要用到坐標(biāo)就用map

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    if(nums1.length<nums2.length){
        const temp = nums1;
        nums1 = nums2;
        nums2 = temp;
    }

    const nums1Set = new Set(nums1);
    const resSet = new Set();

    for(let i = 0;i<nums2.length;i++){
        if(nums1Set.has(nums2[i])){
            resSet.add(nums2[i])
        }
    }

    return Array.from(resSet)
};

快樂數(shù)

題目鏈接/文章講解：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

第一想法

迭代n，運(yùn)用函數(shù)getSum

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
    var sumSet = new Set()
    var getSum = function (n) {
        let sum = 0
        while (n > 0) {
            sum += (n % 10) * (n % 10)
            n = Math.floor(n / 10)
        }
        return sum
    }
    n = getSum(n)
    while(true){
        if(n == 1) return true
        if(sumSet.has(n)) return false
        sumSet.add(n)
        n = getSum(n)
    }

};

兩數(shù)之和

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

第一想法

第一題，之前做的時(shí)候沒學(xué)過哈希表，現(xiàn)在懂了

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    var hash = new Map()
    for (let i = 0; i < nums.length; i++) {
        hash.set(nums[i], i)
    }
    for (let i = 0; i < nums.length; i++) {
        if (hash.has(target - nums[i]) && i !== hash.get(target - nums[i])) return [i, hash.get(target - nums[i])]
    }
};