本文为个人算法学习笔记，原题可根据题号在 leetcode 中查询

数组/字符串

1、合并两个有序数组

题号：88

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

解题方法：逆向双指针

思路：

设置两个指针 p1 和 p2，代表当前正在处理中的 nums1 或 nums2 的位置。每次应用后减 1

以及当前正在处理的元素位置 tail，每次成功处理后减 1

遍历比较两者大小，大的数往 tail 所代表的 nums 的位置存放

const merge = (nums1: number[], m: number, nums2: number[], n: number) => {
  let tail = m + n - 1; //指向当前处理的值（从后往前）
  let p1 = m - 1; //指针指向nums1正在处理的元素
  let p2 = n - 1; //指针指向nums2正在处理的元素

  // 当p1或p2大于-1，说明有数组未完成遍历
  while (p1 > -1 || p2 > -1) {
    let cur: number; // 当次遍历的结果

    // 当p1或p2等于-1，说明对应的数组已经遍历完成
    if (p1 === -1) {
      cur = nums2[p2--];
    } else if (p2 === -1) {
      cur = nums1[p1--];
    }
    // 取出较大的值，当相等时，取任意一个数组的值
    else if (nums1[p1] > nums2[p2]) {
      cur = nums1[p1--];
    } else {
      cur = nums2[p2--];
    }

    // 将值从后往前赋予num1
    nums1[tail--] = cur;
  }

  return nums1;
};

2、移除数组

题号：27

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]

解题方法：双指针

注意点：

1、更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。

2、nums 的其余元素和 nums 的大小并不重要

解题思路：

依次遍历数组，将不同于val的值往前挪即可。使用curIndex记录当前处理的元素，也代表当前与val不同的元素个数

function removeElement(nums: number[], val: number): number {
  let curIndex: number = 0; // curIndex记录当前处理的元素，也代表当前与val不同的元素个数
  for (let i = 0; i < nums.length; i++) {
    // 找不同
    if (nums[i] !== val) {
      nums[curIndex++] = nums[i];
    }
  }
  return curIndex;
}

3、删除有序数组中的重复项

题号：26

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

解题方法： 双指针

解题思路：题目仅检验左边数组的正确性。利用 slow 指针指向当前处理的元素（由于第 1 位始终是最小的，所以 slow = 1 ），fast 指针从第二项开始遍历，如果大于前一项则将其替换掉 slow 的位置的元素

function removeDuplicates(nums: number[]): number {
  let slow = 1;
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast - 1] < nums[fast]) {
      nums[slow++] = nums[fast];
    }
  }
  return slow; //最后一个不重复元素位移后，slow进行了++，所以nums中的重复元素为slow
}

4、删除有序数组中的重复项 2

题号：80

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]

解题方法：双指针

解题思路：定义快慢双指针，慢指针指向当前需要处理的元素(由于前两项要么不同要么相同，符合条件，可以从第三项处理起)，快指针进行遍历。当且仅当 nums[fast] = nums[slow - 1] = nums[slow - 2]，说明当前的 slow 值已存在两次，可以不进行处理。

function removeDuplicates(nums: number[]): number {
  if (nums.length <= 2) return nums.length;

  let slow = 2;
  for (let fast = 2; fast < nums.length; fast++) {
    if (nums[slow - 2] !== nums[fast] || nums[slow - 1] !== nums[fast]) {
      nums[slow] = nums[fast];
      slow++;
    }
  }
  return slow;
}

5、多数元素

题号：169

注意：多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素

解决方法：统计次数、排序、投票算法

方式一 ： 排序

解题思路：既然总数一定大于数组 length 的 1/2，那么通过排序后中位数所在的位置一定就是众数。偶数长度：n / 2; 奇数长度：Math.floor(n/2)

function majorityElement(nums: number[]): number {
  nums.sort((a, b) => a - b);
  return nums[Math.floor(nums.length / 2)];
}

方式二：投票算法（推荐）

解题思路：如果把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0，从结果本身可以看出众数比其他数多(对照生活中的投票现象会变得很好理解)

function majorityElement(nums: number[]): number {
  let candidate: number | null = null; //假设为众数，标记为赞成票
  let count = 0; //目前赞成的分数
  for (let i = 0; i < nums.length; i++) {
      // 当赞成票count为0，重新标记赞成票
    if (count === 0) candidate = nums[i];
    candidate === nums[i] ? count++ : count--; //赞成分数+1；不赞成-1
  }
  return candidate as number;
}

6、轮转数组

题号：189

解决方法：新建一个数组存储、翻转数组

方式一：翻转数组

解题思路：将原数组按照不同的位置翻转 3 次

// 反转数组，指定start与end位置
const reverse = (nums: number[], start: number, end: number): void => {
  while (start < end) {
    let temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
};

function rotate(nums: number[], k: number): void {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1); //反转整个数组
  reverse(nums, 0, k - 1); // 反转前k个
  reverse(nums, k, nums.length - 1); // 反转后 n-k 个
}

7、买股票的最佳时机

题号：121

解决方法：双循环暴力解法、一次遍历

方式一：一次遍历

解题思路：最大的收益永远符合以下规则：历史最低价与后来天数中的最高价的差值。所以只要在一次循环中匹配到最低价，再往后遍历到profit < prices[i] - minPrice即是最大收益

function maxProfit(prices: number[]): number {
  let minPrice = prices[0]; //假设历史最低价格
  let profit = 0; //最大收益

  // 找低价位，往后循环匹配更新收益profit 
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] < minPrice) {
        // 重新更新最低价
      minPrice = prices[i];
    } else if (prices[i] - minPrice > profit) {
        // 更新最大收益
      profit = prices[i] - minPrice;
    }
  }

  return profit;
}

8、买股票的最佳时机 2

题号：122

解决方法：遍历计算差值

解题思路：最大利润为每次能够取得的差值相加

function maxProfit(prices: number[]): number {
  let result = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i - 1] < prices[i]) {
      result += prices[i] - prices[i - 1];
    }
  }
  return result;
}

9、H 指数

题号：274

输入：citations = [3,0,6,1,5]
输出：3 

解决方法：排序

解题思路：排序并反向遍历，当 arr[i]>h 时，h++。否则返回 h

function hIndex(citations: number[]): number {
  citations.sort((a, b) => a - b); //排序

  let h = 0;
  // 从后往前遍历，同时递增h。当h>遍历的元素时，说明找到了h指数
  for (let i = citations.length - 1; i >= 0; i--) {
    if (citations[i] > h) {
      h++;
    }
  }
  return h;
}

10、O(1) 时间插入、删除和获取随机元素

题号：380

解决方法：数组与哈希

解题思路：在进行插入操作时，通过 map 记录插入元素的位置，方便后续进行删除操作；在进行删除时，将数组元素与最后一个元素交换，通过 pop 删除。同时需要更新 map 中的数据；在返回随机元素时，利用 Math.random()*nums.length 向下取整，获取 nums 区间中的随机数

class RandomizedSet {
  private nums: number[];
  private map: Map<number, number>;

  constructor() {
    this.nums = [];
    this.map = new Map();
  }

  insert(val: number): boolean {
    // 已存在
    if (this.map.has(val)) return false;

    // 将val插入数组，并使用map记录val在数组中的位置
    this.nums.push(val);
    this.map.set(val, this.nums.length - 1);
    return true;
  }

  remove(val: number): boolean {
    if (!this.map.has(val)) return false;
    // 匹配到val在数组中的位置
    const index = this.map.get(val) as number;
    // 将val挪到数组末尾，并利用pop进行删除(需更新末尾元素在map的位置)
    this.nums[index] = this.nums[this.nums.length - 1];
    this.map.set(this.nums[index], index);

    this.nums[this.nums.length - 1] = val;
    this.nums.pop();
    this.map.delete(val);

    return true;
  }

  getRandom(): number {
    // this.nums的元素数量必定大于等于1
    if (this.nums.length === 1) return this.nums[0];
    const random = Math.floor(Math.random() * this.nums.length);
    return this.nums[random];
  }
}

11、跳跃游戏

题号：55

解决方法：贪心算法

解题思路：

1、遍历数组，计算可到达元素的向右跳的最大值(i + nums[i])

2、遍历过程中如何确定元素可达：i <= rightIndex。当且仅当向右跳的最大元素 rightIndex大于数组的长度时，说明最后一个元素可达。

反之，如果i > rightIndex，说明遍历过程中某一个元素不可达

function canJump(nums: number[]): boolean {
  let rightIndex = 0; //向右跳可达的index

  for (let i = 0; i < nums.length; i++) {
    // 当循环中出现某一个位置不可达，即rightIndex < i,则失败
    if (rightIndex < i) return false;

    // 否则，更新rightIndex
    // （i + num[i] 当前位置加上可以跳跃的位置） 即为 可达最远元素的位置
    rightIndex = Math.max(rightIndex, i + nums[i]);	
  }

  return true;
}

12、跳跃游戏 2

题号：45

区别：跳跃游戏1判断是否能跳跃到最后；跳跃游戏2是判断跳跃到最后所花的最小步数

解决方法：贪心算法

关键点：每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数

1、每次在上次能跳到的范围（end）内选择一个能跳的最远的位置（也就是能跳到 maxPostion 位置的点）作为新的范围（end)

2、循环过程中，每当循环至边界 end(每次能跳跃的最远距离)，step 跳跃次数+1。

3、为避免最后一次跳跃距离正好等于最后一个位置，导致 step 多了一次。所以遍历时直接跳过最后一次

function jump(nums) {
  let end = 0; // 上次跳跃可达范围右边界（下次的最右起跳点）
  let maxPostion = 0; // 目前能跳到的最远位置
  let steps = 0; // 跳跃次数
  for (let i = 0; i < nums.length; i++) {
      // 更新目前元素最远可达位置
    maxPostion = Math.max(maxPostion, i + nums[i]);
    // 到达上次跳跃能到达的右边界了
    if (i === end) {
      end = maxPostion; // 目前能跳到的最远位置变成了下次起跳位置的有边界
      steps++; // 进入下一次跳跃
      
      // 避免最后一次跳跃距离等于最后一个位置，导致step多加了一次
      if (i === nums.length - 1) {
        step--;
      }
    }
  }
  return steps;
}

13、除自身以外数组的乘积

题号：238

解决方法：当前元素的前缀之积 * 当前元素的后缀之积 = 结果

解题思路：当前元素的前缀之积 * 当前元素的后缀之积 = 除自身以外数组的乘积。遍历数组获取到每个元素的前缀之积 L，倒序遍历数组获取到每个元素的后缀之积，LR 两个数组对应位置元素相乘即时 answer

（为了减少时间空间复杂度，可以将 L 的思想直接在 answer 上直接实现，减少了一个数组的空间和一次循环）

function productExceptSelf(nums: number[]): number[] {
  const answer: number[] = []; //看做是L：number[],前缀之积
  for (let i = 0; i < nums.length; i++) {
    if (i === 0) answer[0] = 1;
    else answer[i] = answer[i - 1] * nums[i - 1];
  }

  //R：number[],后缀之积
  const R: number[] = [];
  for (let i = nums.length - 1; i >= 0; i--) {
    if (i === nums.length - 1) R[i] = 1;
    else R[i] = R[i + 1] * nums[i + 1];
  }

  // 当前元素的前缀之积 * 当前元素的后缀之积
  for (let i = 0; i < nums.length; i++) {
    answer[i] = answer[i] * R[i];
  }

  return answer;
}

14、加油站

题号：134

注：可通过 i % n 实现循环。例如数组 n 长度等于 5，3%5 等于 3，5%5等于0，6%5 则等于 1，从而实现循环

解决方法：暴力双循环

实现思路：此解法考虑从每一个位置出发，能否回到出发的那个位置

结果：返回能够跑完一圈的index，所有位置都不能跑完一圈的话返回-1

function canCompleteCircuit(gas: number[], cost: number[]): number {
  let n = gas.length;

  for (let i = 0; i < gas.length; i++) {
    // 汽车起点的位置
    let runIndex = i;
    // 剩余的汽油总量
    let remain = gas[i];

    // 从当前位置开始启动汽车，看当前的油能否到达下一个点
    while (remain - cost[runIndex] >= 0) {
      // 更新油量, (runIndex + 1) % n 表示下一个节点的位置
      remain = remain - cost[runIndex] + gas[(runIndex + 1) % n];
      // 更新下一个开向节点的位置
      runIndex = (runIndex + 1) % n;

      // 如果回到了起点，说明完成了循环
      if (runIndex === i) {
        return i;
      }
    }
  }
  // 没有回到起点，返回-1
  return -1;
}

15、罗马数字转整数

解决方法：映射、循环

实现思路：一般而言只要做好映射关系，遍历输入字符串s的每个字符对应的数值相加即可。需要特殊处理的时，当一个字符小于后一个字符时，则结果为两数相减。在循环中表现为减去较小的值即可

function romanToInt(s: string): number {
  // 映射
  const map = new Map();
  map.set("I", 1);
  map.set("V", 5);
  map.set("X", 10);
  map.set("L", 50);
  map.set("C", 100);
  map.set("D", 500);
  map.set("M", 1000);

  let result = 0;

  // 遍历每个字符，判断大小
  for (let i = 0; i < s.length; i++) {
    const value = map.get(s[i]);
    // 如果当前字符小于下一个字符，小于则减去，大于则加上
    if (i !== s.length - 1 && value < map.get(s[i + 1])) {
      result -= value;
    } else {
      result += value;
    }
  }
  return result;
}

16、整数转罗马数字

题号：12

解决方法：映射、循环

思路：将所有罗马数字的关系整理为映射二维数组，从大到小排序。遍历这个数组，当存在输入整数大于数组的元素时，即存在对应的罗马数字

function intToRoman(num: number): string {
  const valueSymbols: [number, string][] = [
    [1000, "M"],
    [900, "CM"],
    [500, "D"],
    [400, "CD"],
    [100, "C"],
    [90, "XC"],
    [50, "L"],
    [40, "XL"],
    [10, "X"],
    [9, "IX"],
    [5, "V"],
    [4, "IV"],
    [1, "I"],
  ];
  const roman: string[] = [];
  for (const [value, str] of valueSymbols) {
    while (num >= value) {
      num -= value;
      roman.push(str);
    }
    if (num === 0) {
      break;
    }
  }

  return roman.join("");
}

17、最后一个单词的长度

题号：58

方法：反向循环统计

思路：从后往前遍历，只要不是空格那么count+1。当已经统计到了至少一个字母且又遇到了一个空格，说明第一个最后一个单词的长度已经记录完毕

function lengthOfLastWord(s: string): number {
  let count = 0;

  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] !== " ") {
      // 遇到的是字母
      count++;
    } else if (count > 0 && s[i] === " ") {
      // 说明又遇到了空格，跳出整个循环
      break;
    }
  }

  return count;
}

18、最长公共前缀

题号：14

输入：strs = ["flower","flow","flight"]
输出："fl"

解决方法：双循环、sort方法

方法一

function longestCommonPrefix(strs: string[]) {
  if (strs.length === 0) return "";

  // 对string[]的数组进行比较，会逐字符比较（基于 Unicode）
  // 如果一个字符串的某个字符小于另一个字符串的对应字符，则该字符串被认为更小
  // 如果前几个字符都相等，则继续比较后面的字符
  // 如果一个字符串是另一个字符串的前缀，则短的字符串被认为更小
  // ["flower", "flow", "flight"] ==> ["flight", "flow", "flower"]
  strs.sort();

  let ans = "";
  const first = strs[0];
  const end = strs[strs.length - 1];

  // 比较第一个和最后一个字符串的公共前缀
  for (let i = 0; i < first.length; i++) {
    if (first[i] === end[i]) {
      ans += first[i];
    } else {
      break;
    }
  }

  return ans;
}

方法二

解题思路：每次截取 strs 中元素的一位，依次对比。如果当次循环中都相同，那么最终结果加上这个值，否则直接停止整个循环

function longestCommonPrefix(strs: string[]): string {
  if (strs[0].length === 0) return "";
  let result = "";
  let end = strs[0].length - 1; //第一个元素最大的索引
  let index = 0; //记录当前比较的索引

  while (index <= end) {
    let str = strs[0][index];
    for (let i = 0; i < strs.length; i++) {
      // 当不存在当值，或者对比的值不相同，停止整个循环
      if (!strs[i][index] || strs[i][index] !== str) {
        str = "";
        index = end + 1;
        break;
      }
    }
    result += str;
    index++;
  }

  return result;
}

19、反转字符串中的单词

题号：151

输入：s = "the sky is blue"
输出："blue is sky the"

方法：双指针

思路：倒序遍历字符串 s ，记录单词左右索引边界 i , j 。每确定一个单词的边界，则将其添加至单词列表 res 。最终，将单词列表拼接为字符串，并返回即可

function reverseWords(s: string): string {
  s.trim();

  let j = s.length - 1,
    i = j;

  let result: string[] = [];

  while (i >= 0) {
    // 倒序搜索首个空格
    while (i >= 0 && s[i] !== " ") {
      i -= 1;
    }

    // 代码走到这里，i的右边是单词（那么单词的长度是<i+1,j+1>）
    result.push(s.slice(i + 1, j + 1)); // 添加单词

    // 跳过单词间空格
    while (i >= 0 && s[i] === " ") {
      i -= 1;
    }

    // 代码走到这里，i指向了下一个单词的尾字符
    j = i; // j 指向下个单词的尾字符
  }

  return result.join(" ").trim();
}

20、Z字形变换

题号：6

字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P   A   H   N
A P L S I I G
Y   I   R

从左往右逐行读取，产生出一个新的字符串："PAHNAPLSIIGYIR"

解题思路：根据行数初始化一个数组，遍历字符串，依次将遍历到的字符填充到数组对应的位置。当遍历到了需要向上的位置（down为false）时，将填充的位置（index）依次减少。当遍历到了需要向下的位置时（此时index为0），将index依次增加（down为true）

function convert(s: string, numRows: number): string {
    if (numRows <= 1) return s;
    let arr: string[] = new Array(numRows).fill(""); //初始化数组

    let down = true; //记录当前向下还是向上遍历
    let index = 0; //当前遍历的层级（即数组的index）

    for (let i = 0; i < s.length; i++) {
        if (index === 0) down = true;
        arr[index] += s[i];

        // 向下遍历
        if (index !== arr.length - 1 && down) {
            index++;
            down = true;
        } 
        // 向上遍历
        else {
            down = false;
            index--;
        }
    }

    let result = "";
    for (let i = 0; i < arr.length; i++) {
        result += arr[i];
    }

    return result;
}

21、找出字符串中第一个匹配项的下标

题号：28

解题方法：暴力双循环

思路：

1、遍历haystack，判断遍历的值是否等于needle的第一个单词。是的话则进入第二层循环

2、在第二层循环中，依次判断needle的第2、3..n元素是否与haystack对应的元素相等。

3、第二层循环中，当出现对比结果不一致时，则退出第二层循环。循环完needel时每次结果一致时，则找到了结果

function strStr(haystack: string, needle: string): number {
  if (haystack === needle) return 0;
  if (needle.length > haystack.length) return -1;

  let result = -1;

  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle[0]) {
      let len = 1;
      let flag = true;
      while (needle[len]) {
        if (haystack[i + len] !== needle[len]) {
          flag = false;
          len = needle.length;
        }
        len++;
      }
      if (flag) {
        result = i;
        break;
      }
    }
  }

  return result;
}

双指针

22、验证回文串

题号：125

解题方法：倒序判断相等、双指针

解题思路：

方法一：可以排序调非字母数字后，倒序整个str，如相等则是回文串

方法二：双指针定义前后两个指针，分别指向开头和结尾。如果是回文串，那么前后指针同步向中间靠拢过程中的值应该是相同的

function isPalindrome(s: string): boolean {
  let pattern = /[^a-z0-9]/gi;
  s = s.replace(pattern, "");
  s = s.toLowerCase();

  if (s === "") return true;

  let end = s.length - 1;
  let res = false;
  for (let start = 0; start < s.length; start++) {
    if (s[start] !== s[end]) {
      res = false;
      break;
    }

    // 经过上边的判断，说明此时的  s[start] === s[end]

    // 判断是否start与end即将碰撞，分为两种情况：1、s是偶数个数、s是基数个数
    // 1、s.length是偶数, 则start+ 1 === end
    // 2、s.length是基数, 则 start === end
    if (
      (s.length % 2 === 0 && start + 1 === end) ||
      (s.length % 2 === 1 && start === end)
    ) {
      res = true;
      break;
    }

    end--;
  }

  return res;
}

23、判断子序列

题号：392

方法：双指针

思路：两个指针一个指向s，一个指向t。遍历t，判断每个s的元素是否存在于t

function isSubsequence(s: string, t: string): boolean {
  if (s.length > t.length) return false;
  if (!s) return true;
  let curS = 0;
  for (let i = 0; i < t.length; i++) {
    if (t[i] === s[curS]) {
      // 最后一个元素
      if (curS === s.length - 1) return true;
      curS++;
    }
  }
  return false;
}

24、两数之和II-输入有序数组

题号：167

方法：双指针、暴力双循环（不推荐）

要点：题目的数组是递增数组，且必然存在两数之和等于target

思路：设置前后两个指针start、end，计算两者之和。如果值大于target，则end往前移动；如果小于target，则start往后移动。最终就能够找到答案

function twoSum(numbers: number[], target: number): number[] {
  let end = numbers.length - 1;
  let start = 0;
  while (start < end) {
    if (numbers[start] + numbers[end] === target) {
      return [start + 1, end + 1]; // 注意：返回的结果按照题目特殊处理
    } else if (numbers[start] + numbers[end] > target) {
      end--;
    } else {
      start++;
    }
  }

  return null;
}

25、盛水最多的容器

题号：11

解题方法：暴力双循环，双指针

解题思路：双指针置于两端left right，判断两边谁是短板，短板则向内移动，直至两个指针重叠为止。这个过程中不断更新最大值

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxArea = 0;
  while (left !== right) {
    // 更新最大值
    // 短板决定了最大蓄水量
    let newArea = Math.min(height[left], height[right]) * (right - left);
    maxArea = newArea > maxArea ? newArea : maxArea;

    // 向内移动短板
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxArea;
}

26、三数之和

题号：15

实现方法：暴力三次循环、三指针

固定一个指针k，根据情况移动另外两个指针

判断nums[k] + nums[i] + nums[j] === 0，当小于0时，i往右移动；大于0时，j往左移动

解题思路：对数组进行排序，遍历数组。并以left和right分别指定当前遍历索引k的下一项和数组最后一项。在当次循环中不断判断left和right是否有符合的结果与nums[k]相加等于0

function threeSum(nums:number[]) {
  const result:number[][] = [];
  nums = nums.sort((a, b) => a - b);

  for (let k = 0; k < nums.length - 2; k++) {
    if (nums[k] > 0) break; // 意味着三数相加必定大于0
    if (k > 0 && nums[k] == nums[k - 1]) continue; // 已经将 nums[k - 1] 的所有组合加入到结果中,避免重复
    let left = k + 1; // 小值
    let right = nums.length - 1; // 大值

    while (left < right) {
      let sum = nums[k] + nums[left] + nums[right];
      if (sum < 0) {
        // 跳过相同值，避免记录到重复组合
        while (left < right && nums[left] == nums[++left]); // 该写法循环直到匹配到不同于当前left的值
      } else if (sum > 0) {
        while (left < right && nums[right] == nums[--right]);
      } else {
        result.push([nums[k], nums[left], nums[right]]);
        while (left < right && nums[left] == nums[++left]);
        while (left < right && nums[right] == nums[--right]);
      }
    }
  }
  return result;
}

哈希表

27、赎金信

题号：383

重点理解：cnt[c.charCodeAt(0) - "a".charCodeAt(0)]，每个字母在Unicode表的位置是唯一的且字母表中的字母都是递增的，减去"a".charCodeAt(0)可以生成一个字母唯一确定的数字

例如：如何唯一确定z代表的数字并统计, cnt[c.charCodeAt(0) - "a".charCodeAt(0)]++

cnt[122 - 97] = 0 + 1， 所有cnt[25] = 1表示有一个z

const canConstruct = function (ransomNote: string, magazine: string) {
  // 子集长度大于父集，必然无法由父集构成
  if (ransomNote.length > magazine.length) return false;

  // 生成26个字母的数组，用0填充
  const cnt = new Array(26).fill(0);

  // 统计父集每个字母的出现个数
  for (const c of magazine) {
    cnt[c.charCodeAt(0) - "a".charCodeAt(0)]++;
  }

  // 统计子集每个字母从父集中减去
  for (const c of ransomNote) {
    cnt[c.charCodeAt(0) - "a".charCodeAt(0)]--;

    // 当出现父集的某个字母被减到了负数，说明子集完全由父集构成
    if (cnt[c.charCodeAt(0) - "a".charCodeAt(0)] < 0) {
      return false;
    }
  }
  return true;
};

28、同构字符串

题号：205

输入：s = "egg", t = "add"
输出：true

注意：t.length == s.length

解题方法：双射

思路：创建两个s和t的映射，实现以下逻辑s(a) ---> t(b) t(b) ---> s(a)

遍历整个s字符串，遍历过程中形成映射关系。如果出现s(a) !== t(b)的关系，或者t(b) !== s(a)，则说明不同构

const isIsomorphic = function (s: string, t: string) {
  const sMaps: Record<string, any> = {};
  const tMaps: Record<string, any> = {};

  for (let i = 0; i < s.length; i++) {
    const sVal = s[i];
    const tVal = t[i];

    // 在已有的映射关系中判断
    if (
      (sMaps[sVal] && sMaps[sVal] !== tVal) ||
      (tMaps[tVal] && tMaps[tVal] !== sVal)
    ) {
      return false;
    }

    // 形成映射关系
    sMaps[sVal] = tVal;
    tMaps[tVal] = sVal;
  }
  return true;
};

29、单词规律

题号：290

实现方法：hash映射（双射，与同构字符串同思路）

解题思路：创建两个映射，分别保存规律映射单词，单词映射规律。遍历规律或单词，当出现已存在的映射关系时，判断是否符合之前存的两个映射关系

function wordPattern(pattern, s) {
    const words = s.split(" ");
    const pMap = {};
    const sMap = {};
    if (pattern.length !== words.length) return false;
  
    for (let i = 0; i < words.length; i++) {
      let skey = words[i];
      let pkey = pattern[i];
  
      if (
        (sMap.hasOwnProperty(skey) && sMap[skey] !== pkey) ||
        (pMap.hasOwnProperty(pkey) && pMap[pkey] !== skey)
      ) {
        return false;
      }
  
      sMap[skey] = pkey;
      pMap[pkey] = skey;
    }
    return true;
}

30、有效的字母异位词

题号：242

方法：与赎金信解法类似，通过映射

思路：构建26个字母的统计数组，初始为0。遍历s，统计对应字母的个数。同时也是遍历s，减去对应字母的个数。当出现统计数字某个元素小于0时，说明两者不是异位单词

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const alpha = new Array(26).fill(0);

  for (let i = 0; i < s.length; i++) {
    alpha[s[i].charCodeAt(0) - "a".charCodeAt(0)]++;
    alpha[t[i].charCodeAt(0) - "a".charCodeAt(0)]--;
  }

  for (let i = 0; i < alpha.length; i++) {
    if (alpha[i] < 0) return false;
  }

  return true;
}

31、字母异位分组

题号：49

方法：单词排序

思路：将单词数组的单词提取出来，进行排序后属于异位单词的字符串会变成一样的单词。设置一个map，用排序后的单词作为key进行分组。value的值为一个数组，数组存放原单词。最后重置为二维数组即可

const groupAnagrams = function (strs: string[]): string[][] {
  let map = new Map();
  for (let i = 0; i < strs.length; i++) {
    // 拆分单词，并按照单词进行排序
    const arr = Array.from(strs[i]);
    arr.sort();

    // 重新合并单词
    let key = arr.join("");

    // 以单词为key创建一个数组
    let mapArr = map.get(key) || [];

    // 将原单词(即异位单词)推入数组
    mapArr.push(strs[i]);

    // 设置映射关系
    map.set(key, mapArr);
  }

  return Array.from(map.values());
};

32、两数之和

题号：1

方法：暴力双循环（不推荐）、哈希表

思路：将数组的每一个作为key，index作为值进行映射。那么map必然存在一个key等于目标值target - 当前遍历的值。

提示：如果不好理解，也可拆分成独立的两次循环。第一次形成map，第二次查找值

const twoSum = function (nums: number[], target: number) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (map.get(target - nums[i]) !== undefined) {
      return [map.get(target - nums[i]), i];
    }
    map.set(nums[i], i);
  }
};

33、快乐数

题号：202

解题方法：用哈希集合检测循环

解题思路：创建一个函数用于数位分离求平方和，当函数生成的新值不存在于哈希中时，添加它；存在时则说明进入了一个循环中

const isHappy = function (n) {
  // 获取下一个值
  let getNext = function (n) {
    return n
      .toString()
      .split("")
      .map((i) => i ** 2)
      .reduce((a, b) => a + b);
  };

  const set = new Set();
  // 当set中存在了n，说明进入了死循环
  while (n !== 1 && !set.has(n)) {
    set.add(n);
    n = getNext(n);
  }

  // 当n不能再进入循环时，说明要么n等于1，或者n已经存在于set
  return n === 1;
};

34、存在重复元素 2

题号：219

输入：nums = [1,2,3,1], k = 3
输出：true
// 要求：满足 nums[i] == nums[j] 且 abs(i - j) <= k

解题方法：哈希

思路：遍历过程中，设置map值（key为值，value为序号）。在后续的遍历中如果判断到当前值已存在于map中，说明两者值相同。比较绝对值是否大于k即可

function containsNearbyDuplicate(nums: number[], k: number): boolean {
  const map = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i]) && i - map.get(nums[i])! <= k) {
      return true;
    }
    map.set(nums[i], i);
  }

  return false;
}

35、最长连续序列

题号：128

解题方法：哈希表

解题思路：解题思路在于能够通过num - 1来判断num是否是连续的第一个数，如果是不断的推衍这个数加一是否存在于set中，在这个过程中不断更新最大长度

function longestConsecutive(nums: number[]): number {
  const set = new Set<number>(nums); //转为set结构，并去重
  let res = 0;

  for (let num of set) {
    // 说明此num是连续的第一个数
    if (!set.has(num - 1)) {
      let currentMaxLen = 1; //记录当前数字的最大连续长度
      let currentNum = num; //当前遍历的num值（不断+1）

      // 如果set中有连续的数+1
      while (set.has(currentNum + 1)) {
        currentMaxLen++;
        currentNum++;
      }

      // 不断更新最大长度
      res = Math.max(res, currentMaxLen);
    }
  }
  return res;
}