Appearance
力扣100题
1 两数之和-简单
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]方法1-暴力解法
利用两次循环，第一层遍历原数组，第二层从 i + 1 开始，依次遍历原数组，直到查找到结果
js
var twoSum = function (nums, target) {
const result = [];
for (let i = 0, len = nums.length; i < len; i++) {
// 因为题目要求不能使用两次相同的元素，所以从 i + 1 可以理论上减少后续查找的次数
for (let j = i + 1; j < len; j++) {
if (nums[i] + nums[j] === target) {
result.push(i, j);
break;
}
}
}
return result;
};方法2-优化算法
原理：利用map来存储遍历过的数字，然后利用目标值减去遍历的当前数字，得到的差去查找，找到返回
js
var twoSum = function (nums, target) {
// 利用目标值减去当前数字的值 然后去map里面查找是否存在来判断
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const rest = target - nums[i];
if (map.has(rest)) {
return [map.get(rest), i];
}
map.set(nums[i], i);
}
return [-1, -1];
};2 两数相加-中等
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]方法1-遍历
js
/**
* Definition for singly-linked list.
* }
*/
function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
let n1 = 0
let n2 = 0
let carry = 0 // 进位信息
let head = null
let tail = null
while (l1 || l2) {
n1 = l1 != null ? l1.val : 0
n2 = l2 != null ? l2.val : 0
// 求和
let sum = n1 + n2 + carry
if (!head) {
// 第一个节点，头和尾节点是同一个
head = tail = new ListNode(sum % 10)
} else {
// 尾结点的next指向新节点
tail.next = new ListNode(sum % 10)
// 然后将尾节点往后挪一个
tail = tail.next
}
// 求余数并向下取整
carry = Math.floor(sum / 10)
// 两个节点同时往后挪
if (l1) {
l1 = l1.next
}
if (l2) {
l2 = l2.next
}
}
// 最后一个余数如果大于0需要创建一个新节点
if (carry > 0) {
tail.next = new ListNode(carry)
}
return head
};3 无重复字符的最长子串-中等
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。方法1-滑动窗口
双指针 + map/set表
js
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
if (s.length === 0) {
return 0;
}
// 最长子串的长度
let result = 0;
// 滑动窗口的左边界
let left = 0;
// 用于存储字符及其在字符串中的位置
const charMap = {};
for (let right = 0; right < s.length; right++) {
const char = s[right];
// 如果字符已在charMap中，并且其位置大于或等于当前窗口的左边界，
// 则移动左边界到该字符的下一个位置
if (charMap[char] >= left) {
left = charMap[char] + 1;
}
// 更新字符在charMap中的位置
charMap[char] = right;
// 更新最长子串长度
result = Math.max(result, right - left + 1);
}
return result;
};Set优化版本
js
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
if (s.length === 0) {
return 0;
}
let left = 0;
let right = 0;
let set = new Set();
let max = 0;
// 利用set进行优化
while (right < s.length) {
if (!set.has(s[right])) {
set.add(s[right]);
max = Math.max(max, set.size);
right++;
} else {
set.delete(s[left]);
left++;
}
}
return max;
};4 寻找两个正序数组的中位数-困难
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5方法1-暴力求解
最容易想到的：先合并数组，然后排序，利用数学公式--求中位数，很高效
js
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
let result = 0;
// 合并数组并排序
const nums = [...nums1, ...nums2].sort((a, b) => a - b);
// 判断数组长度是否为偶数，如果是，则取中间两个数的平均值，否则取中间数的值
const len = nums.length;
if (len % 2 === 0) {
// 偶数： 取中间两个数的平均值
let center = Math.floor(len / 2);
result = (nums[center] + nums[center - 1]) / 2;
} else {
// 奇数：取中间数的值
result = nums[Math.floor(len / 2)];
}
// 保留5位小数
return result;
};方法2-二分查找
js
5 最长回文子串-中等
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"方法1-中心扩散
遍历每个字符串，分别以每个字符串为中心，向两边扩散，分别得到奇数和偶数的回文串
js
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
// 判断字符长度大于2直接返回s
if (s.length < 2) {
return s;
}
// 遍历字符串，每个字符中心扩散两次
let ans = "";
for (let i = 0; i < s.length; i++) {
// 长度为奇数，从中心向两边扩展
// 以当前字符为中心，分别扩散左右两个字符，"aba"
let left = i - 1;
let right = i + 1;
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
// 判断是否大于ans
if (right - left - 1 > ans.length) {
ans = s.slice(left + 1, right);
}
// 长度为偶数，从中心向两边扩展
// 以当前字符和相邻字符为中心，分别扩散左右两个字符，"abba"
left = i;
right = i + 1;
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
if (right - left - 1 > ans.length) {
ans = s.slice(left + 1, right);
}
}
return ans;
};6 Z 字形变换-中等
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I示例 3：
输入：s = "A", numRows = 1
输出："A"题目分析
numRows：三行
分为4个字母一组，规律: （3 -1）X 2 = 4 》 （numRows - 1） x 2
numRows：四行
分为6个字母一组，规律: （4 -1）X 2 = 6 》 （numRows - 1） x 2
方法1-找规律
难点在于找到斜线方向的位置
js
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function (s, numRows) {
if (numRows == 1) {
return s;
}
//convs[i]记录转换后第i行的字符串
let convs = new Array(numRows).fill("");
// 计算分组个数
let groupNum = 2 * (numRows - 1);
for (let i = 0; i < s.length; i++) {
// 计算字母应该在的行数，即位置
let rowsum = i % groupNum;
if (rowsum < numRows) {
// 如果0 ~ numRows - 1行，则直接加到对应位置
convs[rowsum] += s[i];
} else {
// 难点：如果超过行数，就要找规律，然后发现 分组数量减去取模的余数，刚好就是对应的位置
convs[groupNum - rowsum] += s[i];
}
}
return convs.join("");
};7 整数反转-中等
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321示例 2：
输入：x = -123
输出：-321示例 3：
输入：x = 120
输出：21示例 4：
输入：x = 0
输出：0方法1-取模反转
拿这个整数的 末尾数字 以12345为例，先拿到5，再拿到4，之后是3，2，1，按这样的顺序就可以反向拼接处一个数字了，也就能达到 反转 的效果。 怎么拿末尾数字呢？好办，用取模运算就可以了
js
/**
* @param {number} x
* @return {number}
*/
var reverse = function (x) {
let res = 0;
while (x != 0) {
// 取模，留下个位数
const digit = x % 10;
// 乘以10 + 取模的个位数
res = res * 10 + digit;
// 余数除以10 正数向下取整----负数需要向上取整，比如-3726/10 = -372
// x = ~~(x / 10)
x = x > 0 ? Math.floor(x / 10) : Math.ceil(x / 10);
// 判断一下边界条件
if (res < Math.pow(-2, 31) || res > Math.pow(2, 31) - 1) {
return 0;
}
}
return res;
};8 字符串转换整数 (atoi)-中等
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。
函数 myAtoi(string s) 的算法如下：
- **空格：**读入字符串并丢弃无用的前导空格（
" "） - **符号：**检查下一个字符（假设还未到字符末尾）为
'-'还是'+'。如果两者都不存在，则假定结果为正。 - **转换：**通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
- **舍入：**如果整数数超过 32 位有符号整数范围
[−231, 231 − 1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于−231的整数应该被舍入为−231，大于231 − 1的整数应该被舍入为231 − 1。
返回整数作为最终结果。
示例 1：
**输入：**s = "42"
**输出：**42
**解释：**加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
带下划线线的字符是所读的内容，插入符号是当前读入位置。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："42"（读入 "42"）
^示例 2：
**输入：**s = " -042"
输出：-42
解释：
第 1 步：" -042"（读入前导空格，但忽视掉）
^
第 2 步：" -042"（读入 '-' 字符，所以结果应该是负数）
^
第 3 步：" -042"（读入 "042"，在结果中忽略前导零）
^示例 3：
**输入：**s = "1337c0d3"
**输出：**1337
解释：
第 1 步："1337c0d3"（当前没有读入字符，因为没有前导空格）
^
第 2 步："1337c0d3"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："1337c0d3"（读入 "1337"；由于下一个字符不是一个数字，所以读入停止）
^示例 4：
**输入：**s = "0-1"
**输出：**0
解释：
第 1 步："0-1" (当前没有读入字符，因为没有前导空格)
^
第 2 步："0-1" (当前没有读入字符，因为这里不存在 '-' 或者 '+')
^
第 3 步："0-1" (读入 "0"；由于下一个字符不是一个数字，所以读入停止)
^示例 5：
**输入：**s = "words and 987"
**输出：**0
解释：
读取在第一个非数字字符“w”处停止。
提示：
0 <= s.length <= 200s由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-'和'.'组成
方法1- 取巧方法
题目正好和前端的 parseInt 方法规则一致，直接使用
js
console.log(parseInt("123")); // 输出: 123
console.log(parseInt(" -42")); // 输出: -42
console.log(parseInt("4.8")); // 输出: 4，因为解析停止在'.'
console.log(parseInt("words and 987")); // 输出: NaN，因为无法解析为整数js
/**
* @param {string} s
* @return {number}
*/
var myAtoi = function (s) {
const number = parseInt(s, 10);
if (isNaN(number)) {
return 0;
} else if (number < Math.pow(-2, 31) || number > Math.pow(2, 31) - 1) {
return number < Math.pow(-2, 31) ? Math.pow(-2, 31) : Math.pow(2, 31) - 1;
} else {
return number;
}
};方法2-状态机
js
/**
* @param {string} s
* @return {number}
*/
var myAtoi = function (s) {
// 结果
let result = 0;
// 符号标识
let sign = 1;
// 索引序号
let index = 0;
// 空格
let blank = " ";
// 忽略前导空白字符
while (blank.includes(s[index])) {
index++;
}
// 处理正负号
if (s[index] === "-") {
sign = -1;
index++;
} else if (s[index] === "+") {
index++;
}
// 解析数字部分
while (index < s.length && /[0-9]/.test(s[index])) {
// 将字符转换为数字并累加到结果中
result = result * 10 + (s[index] - "0") * sign;
index++;
// 判断边界条件
if (result <= Math.pow(-2, 31)) {
return Math.pow(-2, 31);
}
console.log(result);
if (result >= Math.pow(2, 31) - 1) {
return Math.pow(2, 31) - 1;
}
}
return result; // 应用符号并返回结果
};方法3-利用正则匹配
js
/**
* @param {string} s
* @return {number}
*/
var myAtoi = function (s) {
//利用正则匹配
const str = s.trim().match(/^[-|+]{0,1}[0-9]+/);
// 范围判断
if (str === null) {
return 0;
}
const result = Number(str[0]);
if (result >= Math.pow(2, 31) - 1) {
return Math.pow(2, 31) - 1;
} else if (result <= Math.pow(-2, 31)) {
return Math.pow(-2, 31);
}
return result;
};9 回文数-简单
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，
121是回文，而123不是。
示例 1：
输入：x = 121
输出：true示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。方法1-直接求解
字符串分割 + 反转 + 拼接 然后与原字符对比
js
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function (x) {
if (x < 0) return false;
var strx = String(x);
return strx.split("").reverse().join("") === strx ? true : false;
};10 正则表达式匹配
11 盛最多水的容器-中等
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明：**你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：
输入：height = [1,1]
输出：1方法1-双指针
分解从左右两边向中间靠近，分别计算长度 X 高度
js
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
if (height.length === 0) {
return 0;
}
let left = 0;
let right = height.length - 1;
let result = 0;
// 双指针，截取中间的字符排序后对比
// 然后左右指针同步移动到，右指针等于字符串长度即可
while (left <= right) {
let s = (right - left) * Math.min(height[left], height[right]);
result = Math.max(s, result);
if (height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return result;
};12 整数转罗马数字-简单
七个不同的符号代表罗马数字，其值如下：
| 符号 | 值 |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：
- 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
- 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (
V) 减 1 (I):IV，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。 - 只有 10 的次方（
I,X,C,M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。
给定一个整数，将其转换为罗马数字。
示例 1：
**输入：**num = 3749
输出： "MMMDCCXLIX"
解释：
3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC 由于 500 (D) + 100 (C) + 100 (C)
40 = XL 由于 50 (L) 减 10 (X)
9 = IX 由于 10 (X) 减 1 (I)
注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位示例 2：
**输入：**num = 58
输出："LVIII"
解释：
50 = L
8 = VIII示例 3：
**输入：**num = 1994
输出："MCMXCIV"
解释：
1000 = M
900 = CM
90 = XC
4 = IV提示：
1 <= num <= 3999
方法1-穷举-取模法-硬编码
数字小于3999，可以把个位 、十位、百位、千位的整数都列一面，然后取模匹配
第一步：梳理题目 得到字母与数字的对应关系
第二步：根据以上13个符号，分别凑出一张硬编码的数字表，0对应空字符
第三步：利用模运算和除法运算，我们可以得到 num 每个位上的数字：
js
thousands_digit = num / 1000
hundreds_digit = (num % 1000) / 100
tens_digit = (num % 100) / 10
ones_digit = num % 10第四步：根据 num 每个位上的数字，在硬编码表中查找对应的罗马字符，并将结果拼接在一起，即为 num 对应的罗马数字。
js
/**
* @param {number} num
* @return {string}
*/
var intToRoman = function (num) {
const thousands = ["", "M", "MM", "MMM"];
const hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
const tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
const ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
const roman = [];
// 千位
roman.push(thousands[Math.floor(num / 1000)]);
// 百位
roman.push(hundreds[Math.floor((num % 1000) / 100)]);
// 十位
roman.push(tens[Math.floor((num % 100) / 10)]);
// 个位
roman.push(ones[num % 10]);
return roman.join("");
};13 罗马数字转整数-简单
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。X可以放在L(50) 和C(100) 的左边，来表示 40 和 90。C可以放在D(500) 和M(1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
示例 1:
输入: s = "III"
输出: 3示例 2:
输入: s = "IV"
输出: 4示例 3:
输入: s = "IX"
输出: 9示例 4:
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.示例 5:
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.提示：
1 <= s.length <= 15s仅含字符('I', 'V', 'X', 'L', 'C', 'D', 'M')- 题目数据保证
s是一个有效的罗马数字，且表示整数在范围[1, 3999]内 - 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
- IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
方法1- 暴力求解
js
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function (s) {
const symbolMap = {
I: 1,
V: 5,
X: 10,
L: 50,
C: 100,
D: 500,
M: 1000,
};
let ans = 0;
const len = s.length;
for (let i = 0; i < len; i++) {
debugger;
if (i + 1 < len && symbolMap[s[i]] < symbolMap[s[i + 1]]) {
// 小数在左，大数在右，需要减去小数
ans -= symbolMap[s[i]];
} else {
// 大数在左，小数在右，需要加上小数
ans += symbolMap[s[i]];
}
}
return ans;
};14 最长公共前缀-简单
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。提示：
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]如果非空，则仅由小写英文字母组成
方法1- 横向比较
js
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
if (strs.length == 0) return "";
let prefix = strs[0];
for (let i = 1; i < strs.length; i++) {
// 如果没有包含第一个字符串，就遍历后面的所有字符串，每个字符串都截取一个相同的字符串
while (!strs[i].startsWith(prefix)) {
// 每次从末尾截掉一个字符串，逐个往前进行截取
prefix = prefix.substring(0, prefix.length - 1);
if (prefix.length === 0) return "";
}
}
return prefix;
};方法2-纵向比较
js
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
if (strs.length === 0) return "";
// 纵向比较，先假定第一个是最长的公共串
for (let i = 0; i < strs[0].length; i++) {
const char = strs[0][i];
// 从下标为1的字符开始，纵向比对每一个字符串的对应位置的字符
for (let j = 1; j < strs.length; j++) {
// i === strs[j].length 如果后续字符串中有比第一个长度小的，就以端的为主返回
// strs[j][i] !== char 纵向比对每一个字符串
if (i === strs[j].length || strs[j][i] !== char) {
return strs[0].substring(0, i);
}
}
}
// 只有一个就返回
return strs[0];
};15 三数之和-中等
给你一个整数数组 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]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
方法1-双指针
js