Skip to main content

哈希表

什么时候使用哈希法​

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

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

有效的字母异位词​

题号242. 有效的字母异位词

思考

  1. 这道题目可以使用数组和Map来做，核心在于使用哈希表来统计字母出现的次数
  2. 写法上有个细节是要让字符串变为ASCII码使用在Object.charCodeAt这个方法
  3. 数组就是简单的哈希表
方法一 数组​
function isAnagram(s: string, t: string): boolean {
    let r:number[] = new Array(26).fill(0)
    for(let i of s){
        r[i.charCodeAt(0)-'a'.charCodeAt(0)]++
    }
    for(let i of t){
        r[i.charCodeAt(0)-'a'.charCodeAt(0)]--
    }
    return r.every(item=>item===0)
};
方法二 Map​
function isAnagram(s: string, t: string): boolean {
  const len1 = s.length;
  const len2 = t.length;

  // 如果两个字符串长度不同，直接返回 false
  if (len1 !== len2) {
    return false;
  }

  const dic: Map<string, number> = new Map();

  // 统计字符串 s 中字符的出现次数
  for (let i = 0; i < len1; i++) {
    const char = s.charAt(i);
    dic.set(char, (dic.get(char) || 0) + 1);
  }

  // 在字符串 t 中减少字符的出现次数
  for (let i = 0; i < len2; i++) {
    const char = t.charAt(i);
    const count = dic.get(char);
    if (count === undefined || count === 0) {
      // 字符在 t 中出现次数大于在 s 中，或在 s 中没有出现过，直接返回 false
      return false;
    }
    dic.set(char, count - 1);
  }

  // 遍历字典，如果所有字符的出现次数都为 0，则返回 true，否则返回 false
  for (const count of dic.values()) {
    if (count !== 0) {
      return false;
    }
  }

  return true;
}

两个数组的交集​

题号349. 两个数组的交集

思考

  1. 思路和字母异位差不多都是计数
  2. 如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费
方法一 正常解法​
function intersection(nums1: number[], nums2: number[]): number[] {
    let resSet: Set<number> = new Set(),
        nums1Set: Set<number> = new Set(nums1);
    for (let i of nums2) {
        if (nums1Set.has(i)) {
            resSet.add(i);
        }
    }
    return Array.from(resSet);
};
方法二 骚操作​
function intersection(nums1: number[], nums2: number[]): number[] {
    return Array.from(new Set(nums1.filter(i => nums2.includes(i))))
};
方法三 Map​
function intersection(nums1: number[], nums2: number[]): number[] {
    let r = new Map(),
        result = []
    for(let i of nums1){
        if(!r.get(i)){
            r.set(i,0)
        }else{
            r.set(i,r[i]++)
        }
    }
    for(let i of nums2){
        if(r.has(i)&&r.get(i)>=0){
            result.push(i)
            r.set(i,r[i]--)
        }
    }

    return result
};

快乐数​

题号202. 快乐数

思考

  1. 首先要有思路怎么求快乐数，而且要有思路，当n开始循环的时候就应该返回false了，这时候要查询所以使用哈希表
  2. 然后再考虑其他方法
方法一 利用Map来搜索​
function isHappy(n: number): boolean {
    let m = new Map()
    function getNum(n){
        let sum = 0
        while(n){
            sum+=(n%10)**2
            n = Math.floor(n/10)
        }
        return sum
    }
    
    while(true){
        if(m.has(n))return false
        if(n===1)return true
        m.set(n,1)
        n = getNum(n)
    }
};

两数之和​

题号1. 两数之和

思考

本题其实有四个重点：

  1. 为什么会想到用哈希表
  2. 哈希表为什么用map
  3. 本题map是用来存什么的
  4. map中的key和value用来存什么的
function twoSum(nums: number[], target: number): number[] {
    const hashtable = new Map()

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (hashtable.has(complement)) {
            return [hashtable.get(complement), i];
        }

        hashtable.set(nums[i] , i);
    }

    return [];
}

四数相加​

题号454. 四数相加 II

思考

  1. 首先想到暴力解法四次for循环时间复杂度O（n^4）
  2. 后续想到把四个数组分为a+b,c+d 前面那个用Map保存后面那个只要查询Map就行
方法一​
function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    let count = 0,
        m2 = new Map()

    for(let i of nums3){
        for(let j of nums4){
            if(!m2.get(i+j))m2.set((i+j),1)
            else {
                let tmp = m2.get(i+j)+1
                m2.set((i+j),tmp)
                }
        }
    }

    for(let i of nums1){
        for(let j of nums2){
            if(m2.has((-i-j)))count+=m2.get((-i-j))
        }
    }

    return count
};

赎金信​

题号383. 赎金信

思考

  1. 首先想到用Map记录ransonNode中出现每个字母的次数，后面用magazine查询
  2. 由于只有26个字母所以用数组更加优秀一点
方法一​
function canConstruct(ransomNote: string, magazine: string): boolean {
    let m = new Array(26).fill(0),
        base = 'a'.charCodeAt(0)
    for(let i of magazine){
        m[i.charCodeAt(0)-base]++
    }
    for(let i of ransomNote){
        let index = i.charCodeAt(0)-base
        if(!m[index])return false
        m[index]--
    }
    return true
};

三数之和​

题号15. 三数之和

思考

  1. 这道题目由于需要去重，并不适合使用哈希表来做，临界条件很难选择
  2. 使用双指针来做

思路

  1. 由于题目要求返回的是值而不是下标，我们先给数组排序
  2. 然后要明白一个思路，三数之和要是大于零右指针左移，要是小于零左指针右移
  3. 最后就是一些细节去重
方法一​
function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    let length = nums.length;
    let left: number = 0,
        right: number = length - 1;
    let resArr: number[][] = [];
    for (let i = 0; i < length; i++) {
     if (nums[i]>0) {
            return resArr; //nums经过排序后，只要nums[i]>0, 此后的nums[i] + nums[left] + nums[right]均大于0,可以提前终止循环。 
 }
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        left = i + 1;
        right = length - 1;
        while (left < right) {
            let total: number = nums[i] + nums[left] + nums[right];
            if (total === 0) {
                resArr.push([nums[i], nums[left], nums[right]]);
                left++;
                right--;
                while (nums[right] === nums[right + 1]) {
                    right--;
                }
                while (nums[left] === nums[left - 1]) {
                    left++;
                }
            } else if (total < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return resArr;
};
通用方法​
/**
 *  nsum通用解法，支持2sum，3sum，4sum...等等
 *  时间复杂度分析：
 *  1. n = 2时，时间复杂度O(NlogN)，排序所消耗的时间。、
 *  2. n > 2时，时间复杂度为O(N^n-1)，即N的n-1次方，至少是2次方，此时可省略排序所消耗的时间。举例：3sum为O(n^2)，4sum为O(n^3)
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    // nsum通用解法核心方法
    function nSumTarget(nums, n, start, target) {
        // 前提：nums要先排序好
        let res = [];
        if (n === 2) {
            res = towSumTarget(nums, start, target);
        } else {
            for (let i = start; i < nums.length; i++) {
                // 递归求(n - 1)sum
                let subRes = nSumTarget(
                    nums,
                    n - 1,
                    i + 1,
                    target - nums[i]
                );
                for (let j = 0; j < subRes.length; j++) {
                    res.push([nums[i], ...subRes[j]]);
                }
                // 跳过相同元素
                while (nums[i] === nums[i + 1]) i++;
            }
        }
        return res;
    }

    function towSumTarget(nums, start, target) {
        // 前提：nums要先排序好
        let res = [];
        let len = nums.length;
        let left = start;
        let right = len - 1;
        while (left < right) {
            let sum = nums[left] + nums[right];
            if (sum < target) {
                while (nums[left] === nums[left + 1]) left++;
                left++;
            } else if (sum > target) {
                while (nums[right] === nums[right - 1]) right--;
                right--;
            } else {
                // 相等
                res.push([nums[left], nums[right]]);
                // 跳过相同元素
                while (nums[left] === nums[left + 1]) left++;
                while (nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            }
        }
        return res;
    }
    nums.sort((a, b) => a - b);
    // n = 3，此时求3sum之和
    return nSumTarget(nums, 3, 0, 0);
};

四数之和​

题号18. 四数之和

思考

  1. 这道题目就是三数之和的升级版，增加一个for循环
  2. 但是题目有很多细节，比如由于更换了target剪枝需要谨慎
  3. 还有二次去重的时候要注意j>i+1不能写成j>j
  4. 多次练习
function fourSum(nums: number[], target: number): number[][] {
    let result = []
    nums.sort((a,b)=>a-b)
    for(let i=0;i<nums.length;i++){
        if(i>0&&nums[i]===nums[i-1])continue
        for(let j=i+1;j<nums.length;j++){
            let l = j+1,r = nums.length-1,total
            if(j>i+1&&nums[j]===nums[j-1])continue
            while(l<r){
                total = nums[l]+nums[r]+nums[i]+nums[j]
                if(total===target){
                    result.push([nums[l],nums[r],nums[i],nums[j]])
                    r--
                    l++
                    while(l<r&&nums[l]===nums[l-1])l++
                    while(l<r&&nums[r]===nums[r+1])r--
                }
                else if(total<target){
                    l++
                }
                else{
                    r--
                }
            }
        }
    }
    return result
};