Technical blog

IT小白的成长之旅

0%

JS力扣刷题记

发表于 更新于 分类于

前言

如题，打算使用JS从头开始刷leetcode，大致地记录并讲解一下自己的解题思路吧，由于自己的水平原因，所以思路与解法都会比较偏新手向吧，同时不会只关注这一个题的思路，会有一些整体的思路与延伸吧。做这个记录的原因主要是想以新手的角度讲下自己解题遇到的弯路，同时也给自己加深印象吧。开始时可能注释会有些啰嗦，后续会减少不必要的代码解释。打算先写完并理解前150题吧，也并不打算分类的，因为前百题的思路都是经典解题思路，都需要慢慢体会吧。

1、两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。你可以按任意顺序返回答案。转载自两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
    let res = [];
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], i);
        //很简单的题目与逻辑，用map即哈希表的方法辅助查找即可，使用map的set方法构建。
    }
    for (let i = 0; i < nums.length; i++) {
        let newTarget = target - nums[i];
        if (map.has(newTarget) && (map.get(newTarget) !== i)) {
            res.push(i, map.get(newTarget));
            //使用has、get方法分别判断与获取索引
            //这里要注意下，不能两个相同索引相加
            return res;
        }
    }
}

2、两数相加

给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。转载至两数之和

例：输入：l1 = [2,4,3], l2 = [5,6,4]；输出：[7,0,8]；解释：342 + 465 = 807。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const addTwoNumbers = function(l1, l2) {
    let carry = 0;
    //定义进位，
    let sum = new ListNode(0);
    //一般链表题目的输出，需要先新建一个空的头节点，之后以该空结点作链表处理，从而能够避免因链表长度不够导致的报错,后续返回head.next
    let head = sum;
    while (l1 || l2 || carry) {
        let value1 = ((l1 === null) ? 0 : l1.val);
        //其实是在往前面补0，以确保两个加数位数一致
        let value2 = ((l2 === null) ? 0 : l2.val);
        sum.next = new ListNode((value1 + value2 + carry) % 10);
        carry = ((value1 + value2 + carry) >= 10 ? 1 : 0);
        sum = sum.next;
        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }
    return head.next;
}

一般情况下，除了用链表来存储大数以外，在JS中更常用的是用字符串来保存，因此下面我们写一个字符串类型的大数相加，基本的逻辑和链表是一样的，主要是处理的方式不同，这里我就不再赘述原理了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const add = function add(a, b){
  let m = "";
  let n = "";
  let res = [];
  let sum = 0;
  if (a.length > b.length){
    a = '0' + a;
    for (let i = b.length; i < a.length; i++){
      b = '0' + b;
    }
    m = a.split('');
    n = b.split('');
  } 
  else {
    b = '0' + b;
    for (let i = a.length; i < b.length; i++){
      a = '0' + a;
    }
    a = a.split('');
    b = b.split('');
}

  for (let i = a.length - 1; i >= 0; i--) {
    let k = (parseInt(a[i]) + parseInt(b[i]) + sum) % 10;
        res.unshift(k);
        if ((parseInt(a[i]) + parseInt(b[i]) + sum) >= 10) {
            if ((m === n) && (i = t)) {
                res.unshift("1");
            }
            sum = 1
        } else {
            sum = 0;
        }
  }
  let ans = res.join("");
  return ans;
}

3、无重复字符的最长子串

题目：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

例如：输入: s = “abcabcbb”。输出: 3 。解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

思路：像这种子串的问题，最小覆盖子串、字符串的排列、找到字符串中所有字母异位词、无重复字符的最长子串。其实思路基本一致，子串的问题基本都能用滑动窗口的思想来解决。滑动窗口就是双指针的进阶版吧，即维护一个窗口，不断滑动并更新答案。

1、我们在字符串S中使用双指针中的左右指针技巧，初始化left = right = 0，把索引左闭右开区间[left, right)称为一个「窗口」。

2、我们先不断地增加right指针扩大窗口[left, right)，直到窗口中的字符串符合要求（包含了T中的所有字符）。

3、此时，我们停止增加right，转而不断增加left指针缩小窗口[left, right)，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。同时，每次增加left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到right到达字符串S的尽头

第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。下面画图理解一下，needs和window相当于计数器，分别记录T中字符出现次数和「窗口」中的相应字符的出现次数。v

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} s
 * @return {number}
 */
const lengthOfLongestSubstring = function(s) {
    let right = 0, left = 0;
    let length = 0;
    let arr = [];
    //本题的关键在于如何判断是否无重复子串，用indexOf判断新进项即可，或者直接用for循环判断
    while (right < s.length) {
        let index = arr.indexOf(s[right]);
        if (index !== -1) {
            arr.splice(0, index + 1);
            //将重复项之前全部删除,这里其实我们用字符串的操作来代替了滑动窗口的左移
        }
        arr.push(s[right]);
        length = Math.max(length, arr.length);
        right++;
    }
    return length;
};

4、寻找正序数组的两个中位数

题目：给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

思路：暴力求解的话极其简单，直接for循环即可，第一时间会想到就是归并排序最后一步。按照 O(log (m+n)) 时间复杂度的话，面对有序数组的排序，首先想到二分查找，见下方，但是对于两个数组的二分查找该如何实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function binary_search(arr,low, high, key) {
            if (low > high){
                return -1;
            }
            var mid = parseInt((high + low) / 2);
            if(arr[mid] == key){
                return mid;
            }else if (arr[mid] > key){
                high = mid - 1;
                return binary_search(arr, low, high, key);
            }else if (arr[mid] < key){
                low = mid + 1;
                return binary_search(arr, low, high, key);
            }
        };

该题的本质可扩展为寻找两个有序数组的第k小数，不一定是中位数，因此二分查找的本质是partition，每次都剔除k/2个数，且保证这些数都在第k小数左边，即都比第k小数小，然后k = k/2；递归处理后，得到第k小数。

二分查找，关键点在于要partition两个排好序的数组成左右两等份，partition需要满足len(Aleft)+len(Bleft)=(m+n+1)/2 - m是数组A的长度， n是数组B的长度并且partition后 A左边最大(maxLeftA), A右边最小（minRightA), B左边最大（maxLeftB), B右边最小（minRightB) 满足(maxLeftA <= minRightB && maxLeftB <= minRightA)有了这两个条件，那么median就在这四个数中，根据奇数或者是偶数。

奇数：median = max(maxLeftA, maxLeftB)；偶数：median = (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 二分解法
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  // 确保nums1为更短的字符串
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1);
  }
  const m = nums1.length
  const n = nums2.length
  let low = 0
  let high = m
  while(low <= high) {
    const i = low + Math.floor((high - low) / 2)
    const j = Math.floor((m + n + 1) / 2) - i

    const maxLeftA = i === 0 ? -Infinity : nums1[i-1]
    const minRightA = i === m ? Infinity : nums1[i]
    const maxLeftB = j === 0 ? -Infinity : nums2[j-1]
    const minRightB = j === n ? Infinity : nums2[j]

    if (maxLeftA <= minRightB && minRightA >= maxLeftB) {
      return (m + n) % 2 === 1
        ? Math.max(maxLeftA, maxLeftB)
        : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2
    } else if (maxLeftA > minRightB) {
      high = i - 1
    } else {
      low = low + 1
    }
  }
};

5、最长回文子串

题目：给你一个字符串 s，找到 s中最长的回文子串。

思路：最长回文子串的关键，其实通过双指针法也可以来处理，根据上题所述的思路很好进行解决，关键在于如何判定是否是回文子串的函数。但回文子串以及后序的回文子序列等问题，由于前后文联系比较紧密，且多次判断是否符合时间复杂度较大，通常使用动态规划来进行求解。

动态转移方程：dp[i] [j] = dp[i+1] [j-1] && (dp[i] === dp[j])；dp[i] [j]为true指的是：从i到j是回文串。

初始条件：即字符串长度仅为0、1时，必为回文子串，由于有这样的初始条件，初始项比较多，动态转移方程需要修改成:dp[i] [j] = (dp[i] === dp[j] && (j - i < 2 || dp[i+1] dp[j - 1]))。同样，由于初始条件必然有j > i，像这种初始条件的dp，一般都会使用斜向遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = function(s) {
    let res = "";
    let dp = Array.from(new Array(s.length), () => new Array(s.length).fill(0));
    //利用Array.from构建二维数组，或者使用for循环也可
    for (let i = s.length - 1; i >= 0; i--) {
        //这里由于动态转移方程中dp[i][..]依赖于dp[i + 1][..]，因此需要倒着遍历来简化操作
        for (let j = i; j < s.length; j++) {
            //同样，由于初始条件原因，j从靠近i到远离i来遍历
            dp[i][j] = ((s[i] === s[j]) && (j - i < 2 || dp[i+1][j-1]));
            if (dp[i][j] && (j - i + 1 > res.length)) {
                res = s.substring(i, j+1);
                //substring截取字符串，包头不包尾
            }
        }
    }
    return res;
}

6、Z字形变换

题目：将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。请你实现这个将字符串进行指定行数变换的函数：let convert(string s, int numRows)。

P A H N
A P L S I I G
Y I R

思路：关键在于找规律，中间列每列一个，且列数为numsRows-2；因此将一个第一列与后续的中间列作为一个循环，个数为numsRows + numsRows - 2。这样一个循环就能找出来了，再根据每个字符在循环中的位置，分别将其置入不同行。其中仅循环的第一位为第一行，V形排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
const convert = function(s, numRows) {
    if (numRows === 1) {
        return s;
    }
    let rows = new Array(numRows).fill("");//用数组依次存储每一行的字符
    let circle = (2 * numRows - 2);
    for (let i = 0; i < s.length; i++) {
        let x = i % circle;
        rows[Math.min(x, circle - x)] += s[i];
    }
    let ans = rows.join("");
    return ans;
}

7、整数反转

题目：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

思路：在先判断正负号之后，用转字符串再转数组后，使用reverse()方法可以简单实现，但可以思考下用数学方法要如何处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//先试一下数组反转，可以轻松解决
let reverse = function(x) {
    let res = x.toString().split("");
    if (res[0] == "-") {
        res.push("-");//反转后，相当于在前面加-，后面的负号parseInt会忽略掉
    }
    let ans = parseInt(res.reverse().join(""));
    if (ans >= Math.pow(2, 31) || ans <= -Math.pow(2, 31)) {
        ans = 0;
    }ue
    return ans;
}

//再试一下数学方法，关键在于一位位地取余数
let reverse = function(x) {
    let result = 0;
    while (x !== 0) {
        result = x % 10 + result * 10;
        x = (x / 10) | 0;
        //通过位运算符保证取整(无论正负)，同时强制转换为32位有符号整数
    }
    return (result | 0) === result ? result : 0;
    //result | 0 超过32位的整数转换结果不等于自身，可用作溢出判断。
}

8、字符串转整数

题目：请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。

假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。

该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。

假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。在任何情况下，若函数不能进行有效的转换时，请返回 0 。

注意：本题中的空白字符只包括空格字符 ‘ ‘ 。假设我们的环境只能存储 32 位大小的有符号整数。

1
2
3
4
5
6
7
8
9
10
11
//像这种字符串匹配的，先想到使用正则即可，先用trim来去掉前后的空格
/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
    const re = new RegExp(/^(-|\+)?\d+/);
    let str = s.trim().match(re);
    let res = str ? Number(str[0]) : 0;
    return res >= 0 ? Math.min(res, 2**31 - 1) : Math.max(res, -(2**31))
};

9、回文数

题目：判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

思路：跟前面的整数反转一样，简单的思路的话，直接变数组之后，使用reverse()方法之后判断即可；同样也有数学方法来解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//直接用reverse()
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    return x === Number(x.toString().split('').reverse().join(''))
};

//利用数学方法来一步步求余
var isPalindrome = function(x) {
    if (x < 0) {
        return false;
    }
    let result = 0;
    let value = x;
    while (x !== 0) {
        result = result * 10 + x % 10;
        x = (x / 10) | 0;
    }
    if (value = result) {
        return true;
    } else {
        return false;
    }
}

10、正则表达式匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const isMatch = (s, p) => {
  if (s == null || p == null) return false;

  const sLen = s.length, pLen = p.length;

  const dp = new Array(sLen + 1);
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(pLen + 1).fill(false); // 将项默认为false
  }
  // base case
  dp[0][0] = true;
  for (let j = 1; j < pLen + 1; j++) {
    if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];
  }
  // 迭代
  for (let i = 1; i < sLen + 1; i++) {
    for (let j = 1; j < pLen + 1; j++) {

      if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (p[j - 1] == "*") {
        if (s[i - 1] == p[j - 2] || p[j - 2] == ".") {
          dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
        } else {
          dp[i][j] = dp[i][j - 2];
        }
      }
    }
  }
  return dp[sLen][pLen]; // 长sLen的s串 是否匹配 长pLen的p串
};

11、盛水最多的容器

题目：给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。

示例：输入：[1,8,6,2,5,4,8,3,7]；输出：49 ；解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

思路：其实是一个滑动窗口(双指针)类型的题目，暴力法：即穷举所有可能，分别计算面积并保存最大值。

双指针法：从左右两侧开始，将较矮柱子的指针进行移动，而先不移动高柱子的指针，原因：矮柱子选取后如果移动高柱子的话面积是一定会减小的，因为长度距离在变小的时候，此时高度只能小于或等于矮的柱子。因此只能移动矮的柱子这边才有可能使得高度比矮柱子大。所以，每次都移动的是高柱子的指针。这种方法其可以看作是暴力法的剪枝，而不是传统的滑动窗口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = function(height) {
    let left = 0;
    let right = height.length - 1;
    let ans = 0;
    while (left < right) {
        let height1 = Math.min(height[left], height[right]);
        let aquare = height1 * (right - left);
        ans = Math.max(ans, aquare);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return ans;
}

12、整数转罗马数字

思路：整数转罗马数字，比罗马数字转整数要简洁一些，同样关键在于求余的操作。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    var Q = ["", "M", "MM", "MMM"];
    var B = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
    var S = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
    var G = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
    return Q[Math.floor(num/1000)] + B[Math.floor((num%1000)/100)] + S[Math.floor((num%100)/10)] + G[num%10];
};
//利用Math.floor来直接取整数部分，而不是四舍五入

13、罗马数字转整数

思路：罗马数字转整数，首先将所有的组合可能性列出并添加到哈希表中

然后对字符串进行遍历，由于组合只有两种，一种是 1 个字符，一种是 2 个字符，其中 2 个字符优先于 1 个字符

先判断两个字符的组合在哈希表中是否存在，存在则将值取出加到结果 ans 中，并向后移2个字符。不存在则将判断当前 1 个字符是否存在，存在则将值取出加到结果 ans 中，并向后移 1 个字符，遍历结束返回结果 ans。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const romanToInt = function(s) {
    const map = {
        I : 1,
        IV: 4,
        V: 5,
        IX: 9,
        X: 10,
        XL: 40,
        L: 50,
        XC: 90,
        C: 100,
        CD: 400,
        D: 500,
        CM: 900,
        M: 1000
    };
    let ans = 0;
    for(let i = 0;i < s.length;) {
        if(i + 1 < s.length && map[s.substring(i, i+2)]) {
            ans += map[s.substring(i, i+2)];
            i += 2;
        } else {
            ans += map[s.substring(i, i+1)];
            i ++;
        }
    }
    return ans;
};

14、最长公共前缀

题目：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

思路：很简单的题目，一个个的依次找最长公共前缀，先比较前两个，再用得出的公共前缀来匹配下一个；因此需要两层for循环，第一层，用于获取各个字符串，第二层对比每个字符串的各个字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length == 0) {
        return "";
    }
    let res = strs[0];
    for (let i = 1; i < strs.length; i++) {
        let compare = res;
        res = "";
        //前两个先比较,每次比较前修改compare,并重置res
        for (let j = 0; (j < strs[i].length) && (j < compare.length); j++) {
            if (strs[i][j] === compare[j]) {
                res = res + compare[j];
            } else {
                break;
            }
        }
        if (res == "") {
            return "";
        //提前退出的条件，剪枝j
        }
    }
    return res;
}

15、三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。

思路：关键在于如何保证不重复，用常规思路的话，先用三层for循环，之后再用哈希表去重；换一个思路，我们保持三重循环的大框架不变，只需要保证：第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。即这样就只有一种顺序被枚举了，可以先排序，然后再查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const threeSum = function(nums) {
    nums.sort((a, b) => {
        return (a - b);
    });
    let res = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            break;
        }//在算法范畴上，进行逻辑的剪枝，此时后续不可能成立
        let target = -nums[i];
        if ((target + nums[i - 1] == 0) && i > 0) {
            continue;
            //从左往右遍历，此时遇到重复的则直接跳过，使用continue到for的下一个
        }
        //找到一个后，后续的使用双指针来遍历查找，同时去重
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            let n2 = nums[left];
            let n3 = nums[right];
            if (n2 + n3 === target) {
                res.push([nums[i], n2, n3]);
                while (left < right && nums[left] === n2) left++;
                //去重复，后面有相同的则这里直接left++跳过去
                while (left < right && nums[right] === n3) right++;
                //这里在去重时，不要忘记基本的left < right
            } else if(n2 + n3 < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
}

16、最接近的三数之和

题目：给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

思路：同样的思路，排序加双指针的做法能够很好地判断该如何去判断怎么去移动；同样，本题中不需要去考虑重复的问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const threeSumClosest = function(nums, target) {
    nums.sort((a, b) => {
        return (a - b);
    });
    let ans = 0;
    let compare = Infinity;
    for (let i = 0; i < nums.length; i++) {
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            let compare2 = target - nums[left] - nums[right] - nums[i];
            if (Math.abs(compare2) < compare) {
                ans = nums[i] + nums[right] + nums[left];
                compare = Math.abs(compare2)
            }
            if (compare2 < 0) {
                right--;
            } else {
                left++;
            }
        }
    }
    return ans;
}

17、电话号码的组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路：看上去十分容易，本质是一个三叉树的遍历方法，可以用BFS或者DFS。由这个题，我们可以先引申一下深度遍历和广度遍历的思路逻辑与基本方法。

1、DFS回溯（回溯是一种算法思想，一般可以用递归来实现。通俗点讲回溯就是一种试探,类似于穷举,但回溯有“剪枝”功能,）

回溯本质是暴力搜索，在问题的解空间树中，用 DFS 的方式，从根节点出发搜索整个解空间。如果要找出所有的解，则要搜索整个子树，如果只用找出一个解，则搜到一个解就可以结束搜索。类似「找出所有可能的组合」的问题，适合回溯算法。

回溯类题目，有三个关键点：

(1).选择:决定了你每个节点有哪些分支，可以帮助你构建出解的空间树。

(2).约束条件:用来剪枝，剪去不满足约束条件的子树，避免无效的搜索。

(3).目标:决定了何时捕获解，或者剪去得不到解的子树，提前回溯。

回溯法实质:它的求解过程实质上是先序遍历一棵“状态树”的过程。只不过，这棵树不是遍历前预先建立的，而是隐含在遍历过程中。如果认识到这点，很多问题的递归过程设计也就迎刃而解了。【回溯与递归的区别】回溯这个算法思想可以由递归这个算法结构来实现

我们构建一个递归来实现DFS，。递归的关键：递归关系与递归终止条件。（其他的扔给递归）

1、找整个递归的终止条件：递归应该在什么时候结束？2、找返回值：应该给下一级返回什么信息？3、本级递归应该做什么：在这一级递归中，应该完成什么任务？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const letterCombinations = (digits) => {
    if (digits.length === 0) {
        return [];
    }
    const res = [];
    const map = new Map([['2','abc'], ['3','def'],['4','ghi'],['5','jkl'],['6','mno'],['7','pqrs'],['8','tuv'],['9','wxyz']]);

    const dfs = (curStr, i) => {//递归的传递参数包括，当前已经遍历树的结果、以及层数i
        if (i > digits.length - 1) {
            res.push(curStr);
            return;//一个树的递归分支结束
        }
        let letters = map.get(digits[i]);
        for (j of letters) {
            //for in 用于遍历对象,for of用于遍历有Iterator接口的对象,
            dfs(curStr, i+1);
        }
    }

    dfs("", 0);
    return res;
}

2、BFS广度搜索的方法

BFS通常是维护一个队列，即一层层地进行遍历，每次将对应层数的叶子加到之前层上，这里可以使用队列先进先出来解决，先进先出，依次地每次更新对应的下一层的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} digits
 * @return {string[]}
 */
const letterCombinations = (digits) => {
    if (digits.length == 0) {
        return [];
    }
    let res = [];
    let map = new Map([['2','abc'], ['3','def'],['4','ghi'],['5','jkl'],['6','mno'],['7','pqrs'],['8','tuv'],['9','wxyz']]);
    let queue = [];
    queue.push('');
    for (let i = 0; i < digits.length; i++) {//bfs二叉树的层数，就是digits的长度
        let levelSize = queue.length;//获取当前层的节点数，从而能逐个让当前层节点出列，更新接上对应后续节点后再依次入列
        for (let j = 0; j < levelSize; j++) {
            let curStr = queue.shift(); //模拟队列
            let letters = map.get(digits[i]);
            for (let k of letters) {
                queue.push(curStr + k);
            }
        }
    }
    return queue;
}

18、四数之和

题目：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组

思路：其实跟前面的三数之和思路一样，后面两个数可以用双指针法来进行枚举；而前面两个数只能通过两层的for循环来实现。同样，先对数组进行排序，且添加每个数时都要进行重复判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const fourSum = function(nums, target) {
    const quadruplets = [];
    if (nums.length < 4) {
        return quadruplets;
    }
    nums.sort((x, y) => x - y);
    const length = nums.length;
    for (let i = 0; i < length - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;//从左往右遍历，有跟上一条重复的则跳过
        }
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }
        if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
            continue;//上面两种情况都是剪枝，以减少事件复杂度
        }
        for (let j = i + 1; j < length - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue;
            }
            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }
            if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            let left = j + 1, right = length - 1;
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum === target) {
                    quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
                    while (left < right && nums[left] === nums[left + 1]) {
                        left++;
                    }
                    left++;
                    while (left < right && nums[right] === nums[right - 1]) {
                        right--;
                    }
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return quadruplets;
};

19、删除链表的倒数第N个结点

题目:给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？

思路：不要求时间复杂度的话，先扫一遍来确定链表的长度，而后再根据长度找到倒数第N个结点；要使用一趟扫描实现的话，可以使用双指针来进行。第一个指针比第二个快n个，这样第二个指向尾节点时，则第一个指向要删除的结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const removeNthFromEnd = function(head, n) {
    let start = new ListNode;
    //一般先定义一个空结点放到现有的头节点前面，之后以该空结点作链表处理，从而能够避免因链表长度不够导致的报错
    start.next = head;
    let left = start;
    let right = start;
    for (let i = 0; i < n; i++) {
        right = right.next;
    }
    while (right.next != null) {
        left = left.next;
        right = right.next;
    }
    left.next = left.next.next;
    return start.next;
};

20、有效的括号

题目：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

思路：类似于栈的操作，判断很简单，这里就不赘述了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * @param {string} s
 * @return {boolean}
 */
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s.length == 0) {
        return true;
    }
    let compare = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(" || s[i] === "[" || s[i] === "{") {
            compare.push(s[i]);
        }
        else if (s[i] === ")") {
            let a = compare.pop();
            if (a !== "(") {
                return false;
            }
        }
        else if (s[i] === "]") {
            let a = compare.pop();
            if (a !== "[") {
                return false;
            }
        }
        else if (s[i] === "}") {
            let a = compare.pop();
            if (a !== "{") {
                return false;
            }
        }
    }
    if (compare.length == 0) {
        return true;
    } else {
        return false;
    }
};
-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！