LeetCode - 哈希表

PS：按照代码随想录的题单顺序刷题，记录一下。

1. 有效字母异位词

1.1 有效字母异位词

描述

LeetCode242 - 给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。简单

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例1：

输入：s = "anagram", t = "nagaram"
输出：true

思路

使用哈希表保存前一个字符串的字母，遍历另一个字符串，同时更新哈希表。本题可以优化一下，字母最多 26 位，可以直接用数组存，将字母转为数组下标。

242 - 有效字母异位词

var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;
    const table = new Array(26).fill(0)
    for(let str of s) {
        table[str.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    for(let str of t) {
        table[str.charCodeAt(0) - 'a'.charCodeAt(0)]--;
        if(table[str.charCodeAt(0) - 'a'.charCodeAt(0)] < 0) return false;
    }
    return true;
};

1.2 赎金信

描述

LeetCode383 - 给你两个字符串：ransomNote 和 magazine，判断 ransomNote 能不能由 magazine 里面的字符构成。magazine 中的每个字符只能在 ransomNote 中使用一次。简单

示例1：

输入：ransomNote = "aa", magazine = "ab"
输出：false

思路

使用哈希表。需要注意两个字符串长度可以不一样。

383 - 赎金信

var canConstruct = function(ransomNote, magazine) {
    const table = new Array(26).fill(0);
    for(let str of magazine) {
        table[str.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    for(let str of ransomNote) {
        table[str.charCodeAt(0) - 'a'.charCodeAt(0)]--;
        if(table[str.charCodeAt(0) - 'a'.charCodeAt(0)] < 0) {
            return false;
        }
    }
    return true;
};

1.3 字母异位词分组

描述

LeetCode49 - 给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。中等

示例1：

输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]

思路

字母异位词的字母出现次数相同，将字符串各字母出现次数拼接作为哈希表的 key，value 就是相同的字母异位词。

49 - 字母异位词分组

var groupAnagrams = function(strs) {
    const res = {};
    for(let str of strs) {
        const table = new Array(26).fill(0);
        for(let c of str) {
            table[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        res[table] ? res[table].push(str) : res[table] = [str]
    }
    return Object.values(res);
};

1.4 找到字符串中所有的字母异位词

描述

LeetCode438 - 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。中等

示例1：

输入：s = "cbaebabacd", p = "abc"
输出：[0,6]

思路

字符串中找符合条件的子串，首先想到滑动窗口，窗口可以用长度 26 的数组表示，每次滑动时将对应字母的数加 1，当窗口长度满足子串长度时，判断是否是字母异位词，同时将窗口左边的字母数减 1，左指针右移。

438 - 找到字符串中所有的字母异位词

var findAnagrams = function(s, p) {
    const res = []
    const pTable = new Array(26).fill(0);
    for(let c of p) {
        pTable[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    const pStr = pTable.toString();
    const sTable = new Array(26).fill(0);
    // 滑动窗口
    let left = 0, right = 0;
    while(right < s.length) {
        // 加入窗口
        sTable[s[right].charCodeAt(0) - 'a'.charCodeAt(0)]++;
        // 缩小窗口
        if(right - left + 1 === p.length) {
            // 更新res
            if(sTable.toString() === pStr) {
                res.push(left);
            }
            sTable[s[left].charCodeAt(0) - 'a'.charCodeAt(0)]--;
            left++;
        }
        right++;
    }
    return res;
};

2. 两个数组的交集

2.1 两个数组的交集

描述

LeetCode349 - 给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。简单

示例1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

思路

哈希表或排序+双指针。

349 - 两个数组的交集

var intersection = function (nums1, nums2) {
    let set1 = new Set(nums1);
    let set2 = new Set(nums2);
    const res = []

    if (set1.size > set2.size) {
        [set1, set2] = [set2,set1]
    }

    for (let s of set1) {
        if (set2.has(s)) {
            res.push(s)
        }
    }

    return res
};

2.2 两个数组的交集II

描述

LeetCode350 - 给你两个整数数组 nums1 和 nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。简单

示例1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

思路

使用哈希表存第一个数组元素，值是出现次数，遍历第二个数组，如果元素在哈希表中存在，加入结果，并将哈希表的值减 1，如果值为 0 则删除该 key。

350 - 两个数组的交集II

var intersect = function(nums1, nums2) {
  // 长度小的情况能转数组下标就用数组，减少hash耗时
  const map = new Array(1001).fill(0);
  const res = []
  for(let i of nums1) {
    map[i]++;
  }
  for(let i of nums2) {
    if(map[i]) {
      res.push(i);
      map[i]--;
    }
  }
  return res;
};

3. 快乐数

描述

LeetCode202 - 编写一个算法来判断一个数 n 是不是快乐数。简单

「快乐数」定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
• 如果这个过程结果为 1，那么这个数就是快乐数。

示例1：

输入：n = 19
输出：true
解释：
1 ** 2 + 9 ** 2 = 82
8 ** 2 + 2 ** 2 = 68
6 ** 2 + 8 ** 2 = 100
1 ** 2 + 0 ** 2 + 0 ** 2 = 1

思路

哈希表：按算法正常计算，计算结果存到哈希表，如果哈希表内存在则表示不是快乐数，结果为 1 则是。

快慢指针：根据当前元素得出下一元素，可以看成是一种链式结构，问题也就变成了判断链表是否有环，有环则不是快乐数，因此可以使用快慢指针。

202 - 快乐数

// 哈希表
var isHappy = function(n) {
    const map = new Map();
    while(n !== 1) {
        let temp = transfor(n);
        if(map.has(temp)) {
            return false;
        } else {
            map.set(temp, 1)
        }
        n = temp;
    }
    return true;
};

// 快慢指针
var isHappy = function(n) {
    // 快慢指针
    slow = n, fast = transfor(n);
    while(fast !== slow && fast !== 1) {
        slow = transfor(slow);
        fast = transfor(transfor(fast))
    }
    return fast == 1;
};

const transfor = (num) => {
    let res = 0;
    while(num) {
        res += (num % 10) * (num % 10);
        num = Math.floor(num / 10);
    }
    return res;
}

4. 两数之和

描述

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

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

示例1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]

思路

就把遍历过的元素存到哈希表，value 是索引，每次遍历的时候跟目标做差，看哈希表中是否存在。

1 - 两数之和

var twoSum = function(nums, target) {
    const map = new Map();
    for(let i = 0; i < nums.length; i++) {
        let need = target - nums[i];
        if(map.has(need)) {
            return [i, map.get(need)]
        } else {
            map.set(nums[i], i);
        }
    }
};

5. 四数相加II

描述

LeetCode454 - 给你四个整数数组 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 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：两个元组是(0, 0, 0, 1)和(1, 1, 0, 0)

思路

这题可以看成 num1 + num2 == -(num3 + num4)，计算 nums1 和 nums2 中每个元素和作为 key 存到哈希表，value 是出现的次数，再计算 nums3 和 nums4 中元素相加的情况，只要与哈希表中某个 key 相加等于 0，表示有对应 value 种情况符合条件。

454 - 四数相加II

var fourSumCount = function(nums1, nums2, nums3, nums4) {
    const map = new Map();
    let count;
    for(let i = 0; i < nums1.length; i++) {
        for(let j = 0; j < nums2.length; j++) {
            count = nums1[i] + nums2[j];
            map.set(count, (map.get(count) || 0) + 1);
        }
    }
    let res = 0;
    for(let i = 0; i < nums3.length; i++) {
        for(let j = 0; j < nums4.length; j++) {
            count = -(nums3[i] + nums4[j]);
            if(map.has(count)) {
                res += map.get(count)
            }
        }
    }
    return res;
};

6. 三数之和

描述

LeetCode15 - 给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。中等

示例1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

思路

排序+双指针。首先排序，第一层 for 遍历，每次遍历使用 left 指向 i 的后一元素，right 指向最后一个元素，不停移动指针，将符合条件的元素加入结果。本次遍历结束后判断下一位置是否与当前相等，相等则 i++，这步是防止出现重复三元组。

15 - 三数之和

var threeSum = function(nums) {
  const n = nums.length;
  // 先排序
  nums.sort((a, b) => a - b);
  let left, right;
  const res = [];
  for(let i = 0; i < nums.length - 2; i++) {
    left = i + 1, right = n - 1;
    // 剪枝
    if(nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
    if(nums[i] + nums[n - 1] + nums[n - 2] < 0) continue;
    while(left < right) {
      if(nums[left] + nums[right] === -nums[i]) {
        res.push([nums[i], nums[left], nums[right]]);
        left++;
        // 去重
        while(nums[left] === nums[left - 1]) left++;
        right--;
        while(nums[right] === nums[right + 1]) right--;
      } else if (nums[left] + nums[right] > -nums[i]) {
        right--;
        while(nums[right] === nums[right + 1]) right--;
      } else {
        left++;
        while(nums[left] === nums[left - 1]) left++;
      }
    }
    // 去重
    while(nums[i] === nums[i + 1]) {
      i++;
    }
  }
  return res;
};

7. 四数之和

描述

LeetCode18 - 给你一个由 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

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

示例1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

思路

思路跟三数之和类似，首先两个 for 循环确定两个元素，然后用双指针探测另外两个值，期间可以进行剪枝优化。

18 - 四数之和

var fourSum = function(nums, target) {
  const res = [];
  const n = nums.length;
  let left, right;
  // 排序
  nums.sort((a, b) => a - b);
  for(let i = 0; i < n - 3; i++) {
    // 剪枝
    if(nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
    if(nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;

    for(let j = i + 1; j < n - 2; j++) {
      // 剪枝
      if(nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
      if(nums[i] + nums[j] + nums[n - 1] + nums[n -2] < target) continue;

      left = j + 1, right = n - 1;
      let need = target - nums[i] - nums[j];
      while(left < right) {
        if(nums[left] + nums[right] === need) {
          res.push([nums[i], nums[j], nums[left], nums[right]]);
          left++;
          while(nums[left] === nums[left - 1]) left++;
          right--;
          while(nums[right] === nums[right + 1]) right--;
        } else if(nums[left] + nums[right] > need) {
          right--;
          while(nums[right] === nums[right + 1]) right--;
        } else {
          left++;
          while(nums[left] === nums[left - 1]) left++;
        }
      }
      while(nums[j] === nums[j + 1]) {
        j++;
      }
    }
    while(nums[i] === nums[i + 1]) {
      i++;
    }
  }
  return res;
};