哈希表

注：模块区分的并不肯定，有的标题不一定用的哈希法。

数据结构类型：

  1. 数组（标题限制了数值的巨细）
  2. set
  3. map

适用场景：

​ 当咱们需求查询一个元素是否呈现过，或者一个元素是否在调集里的时分，就要第一时间想到哈希法。

1. 有效的字母异位词

标题：

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

​ 留意：若 s 和 t 中每个字符呈现的次数都相同，则称 s 和 t 互为字母异位词。

基本思路：

  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. 两个数组的交集

标题：

​ 给定两个数组 nums1 和 nums2 ，回来 它们的交集 。输出成果中的每个元素一定是 仅有 的。咱们能够 不考虑输出成果的次序 。

要害点：仅有

思路：

  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

标题：

​ 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 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 != j、i != k 且 j != 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

  • a、b、c 和 d 互不相同

  • 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
};