likes
comments
collection
share

哈希表模块算法题

作者站长头像
站长
· 阅读数 26

哈希表

注:模块划分的并不绝对,有的题目不一定用的哈希法。

数据结构类型

  1. 数组(题目限制了数值的大小
  2. set
  3. map

适用场景

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

1. 有效的字母异位词

题目

​ 给定两个字符串 st ,编写一个函数来判断 t 是否是 s 的字母异位词。

注意:若 st 中每个字符出现的次数都相同,则称 st 互为字母异位词。

基本思路

  1. 首先判断两个字符串的长度是否相同
  2. 长度相同,则对这两个字符串中各字符出现的频率进行计数
  3. 对比两个字符串各字符频率是否相等

数据结构:数组

注意点:字符不能直接参与数字运算,需要利用charCodeAt() 方法返回字符的 unicode 编码。(使用 js

代码

  1. 首先定义一个长度为26的数组,数组内所有元素初始化为0
  2. 数组下标 0-25 的位置依次存放 a-z 字符的出现频率
  3. 数组一边对 s 字符串中的出现的字符实现 ++ 操作,一边对 t 字符串中的出现的字符实现 -- 操作,即若二者中字符出现频率相同,则可抵消,最终为0
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
    if (s.length != t.length)
        return false
    let hashArr = new Array(26).fill(0);
    let n = 'a'.charCodeAt()
    for (let i = 0; i < s.length; i++) {
        hashArr[s[i].charCodeAt() - n]++
        hashArr[t[i].charCodeAt() - n]--
    }
    for (let i = 0; i < 26; i++) {
        if (hashArr[i] !== 0)
            return false
    }
    return true
};

2. 两个数组的交集

题目

​ 给定两个数组 nums1nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序

关键点:唯一

思路

  1. 将 nums1 转换成 set 对象
  2. 遍历 nums2,判断其元素是否也存在于 nums1中。若存在,则将其加入到最终的结果对象中(也是 set 对象,用于去重)
  3. 将结果对象转换成数组类型返回

数据结构:set

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
    let set = new Set(nums1)
    let result = new Set()
    for (item of nums2) {
        if (set.has(item)) {
            result.add(item)
        }
    }
    return Array.from(result)
};

3. 两数之和

题目

​ 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

​ 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

​ 你可以按任意顺序返回答案。

思路

  1. 遍历数组。
  2. 判断是否存在与当前数组元素之和为目标值的元素(即一个元素是否在集合里)。

故,使用哈希法。由于既要知道元素值还要知道元素下标,所以使用 map

使用数组和 set 的局限

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

注意:对象的属性可以通过中括号的形式进行访问。

代码

  • 首先初始化一个对象,用于表示 key-value 集合(元素值-元素下标)。
  • 然后遍历数组,若与当前数组元素之和为目标值的元素在集合中,则返回二者对应下标;若不在,则将当前元素添加到集合中,继续遍历。
  1. 使用 Map 对象

    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var twoSum = function (nums, target) {
        let map = new Map()
        for (let i = 0; i < nums.length; i++) {
            if (map.has(target - nums[i]))
                return [i, map.get(target - nums[i])]
            map.set(nums[i], i)
        }
        return []
    };
    
  2. 使用一般对象

    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var twoSum = function (nums, target) {
        let hashMap = {}
        for (let i = 0; i < nums.length; i++) {
            if (hashMap[target - nums[i]] != undefined) 
                return [i, hashMap[target - nums[i]]]
            hashMap[nums[i]] = i
        }
        return []
    };
    

4. 四数相加 II

题目

​ 给你四个整数数组 nums1nums2nums3nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

思路

  1. 先遍历 nums1 和 nums2 ,计算这两个数组的元素之和并记录。
  2. 再遍历 nums3 和 nums4 , 计算这两个数组的元素之和并判断 nums1 和 nums2 的元素之和中是否有与该和之和满足最终条件的并记录。
  3. 由于需要判断 nums1 和 nums2 的元素之和中是否有与 nums3 和 nums4 元素之和满足最终条件的元素,即查询一个元素是否在集合里,所以使用哈希法。
  4. 由于既要记录值,又要记录出现次数,所以使用 map

注意:将 nums1 和 nums2 之和加入 map 时需要对其之前不存在的情况进行处理。

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function (nums1, nums2, nums3, nums4) {
    let map = new Map()
    let count = 0
    for (const i of nums1) {
        for (const j of nums2) {
            map.set(i + j, (map.get(i + j) || 0) + 1)
        }
    }
    for (const i of nums3) {
        for (const j of nums4) {
            count += (map.get(-(i + j)) || 0)
        }
    }
    return count
};

5. 三数之和

题目

​ 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

关键点:去重

思路

  1. 哈希法(不推荐): 两层for循环就可以确定 a 和b 的数值了,然后可以使用哈希法来确定 -(a+b) 是否在数组里出现过,思路是正确的,但是我们有一个非常棘手的问题,就是题目中说的不可以包含重复的三元组。

  2. 双指针法

    • 将数组排序(升序)
    • 利用一层 for 循环确定 a,利用 left 指针确定 b,利用 right 指针确定 c
    • for 循环遍历排序后的数组
    • 如果 a>0,则直接返回;如果 a 重复,则跳过(去重 a)
    • left 初始为 a 的位置 +1,right 初始为数组最后一个元素的位置(固定 a,b、c动)
    • 当 left<right 时,如果 a+b+c>0,则说明数字太大,应移动 right;如果 a+b+c<0,则说明数字太小,应移动 left;如果 a+b+c=0,则收集数据,判断 left、right 接下来的位置数字是否重复,重复则跳过(去重 b、c),不重复则设为新值,进入新的收集过程,直至 left>=right,则一轮循环结束
  • 最终,返回所收集的数据

动画效果:

哈希表模块算法题

代码

双指针法:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    let r = []
    nums.sort((a, b) => a - b)
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) return r
        if (i > 0 && nums[i] === nums[i - 1]) continue
        let left = i + 1
        let right = nums.length - 1
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right]
            if (sum < 0) left++
            else if (sum > 0) right--
            else {
                r.push([nums[i], nums[left], nums[right]])
                while (left < right && nums[left] === nums[left + 1]) left++
                while (left < right && nums[right] === nums[right - 1]) right--
                left++
                right--
            }
        }
    }
    return r
};

6. 四数之和

题目

​ 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

  • 0 <= a, b, c, d < n

  • abcd 互不相同

  • nums[a] + nums[b] + nums[c] + nums[d] == target

    你可以按 任意顺序 返回答案 。

思路:双指针法,延续三数之和的思想,再加一层循环(注意剪枝条件的变化,target 可正可负可为0)

  • 将数组排序(升序)
  • 利用两层 for 循环外层确定 a 内层确定 b,利用 l 指针确定 c,利用 r 指针确定 d
  • 外层 for 循环遍历排序后的数组
  • 如果 a>target&&>0,则直接返回;如果 a 重复,则跳过(去重 a)
  • 内层 for 循环从外层+1开始
  • 如果 a+b>target&&>0,则跳出循环;如果 b 重复,则跳过(去重 b)
  • l 初始为 b 的位置 +1,r 初始为数组最后一个元素的位置(固定 a、b,c、d 动)
  • 当 l<r 时,如果 a+b+c+d>target,则说明数字太大,应移动 right;如果 a+b+c+d<target,则说明数字太小,应移动 left;如果 a+b+c+d=target,则收集数据,判断 left、right 接下来的位置数字是否重复,重复则跳过(去重 c、d),不重复则设为新值,进入新的收集过程,直至 l>=r,则一轮内循环结束
  • 最终,返回所收集的数据

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
    let result = []
    nums.sort((a, b) => a - b)
    for (let i = 0; i < nums.length - 3; i++) {
        if (nums[i] > target && nums[i] > 0) return result
        if (i > 0 && nums[i] === nums[i - 1]) continue
        for (let j = i + 1; j < nums.length - 2; j++) {
            if ((nums[i] + nums[j]) > target && (nums[i] + nums[j]) > 0) break
            if (j > i + 1 && nums[j] === nums[j - 1]) continue
            let l = j + 1, r = nums.length - 1
            while (l < r) {
                let sum = nums[i] + nums[j] + nums[l] + nums[r]
                if (sum < target) l++
                else if (sum > target) r--
                else {
                    result.push([nums[i], nums[j], nums[l], nums[r]])
                    while (nums[l] === nums[l + 1]) l++
                    while (nums[r] === nums[r - 1]) r--
                    l++
                    r--
                }
            }
        }
    }
    return result
};
转载自:https://juejin.cn/post/7272015112819212348
评论
请登录