Leetcode: 0011-0020题速览

本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

遵从开源协议为知识共享 版权归属-相同方式共享 4.0 国际 公共许可证

研一在读备战就业，制此集合便于空闲时间浏览，有任何疑惑问题欢迎讨论，共同进步

leetcode.cn/problems/container-with-most-water" rel="nofollow">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

 

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

难度：中等

标签：贪心,数组,双指针

解法

方法一：双指针

一开始，我们考虑相距最远的两个柱子所能容纳水的容量。水的宽度是两根柱子之间的距离，而水的高度取决于两根柱子之间较短的那个。

当前柱子是最两侧的柱子，水的宽度最大，其他的组合，水的宽度都比这个小。不妨假设左侧柱子的高度小于等于右侧柱子的高度，那么水的高度就是左侧柱子的高度。如果我们移动右侧柱子，那么水的宽度就减小了，而水的高度却不会增加，因此水的容量一定减少。所以我们移动左侧柱子，更新最大容量。

循环此过程，直到两个柱子相遇。

时间复杂度 $O(n)$，其中 $n$ 是数组 height 的长度。空间复杂度 $O(1)$。

Python3

class Solution:def maxArea(self, height: List[int]) -> int:i, j = 0, len(height) - 1ans = 0while i < j:t = (j - i) * min(height[i], height[j])ans = max(ans, t)if height[i] < height[j]:i += 1else:j -= 1return ans

Java

class Solution {public int maxArea(int[] height) {int i = 0, j = height.length - 1;int ans = 0;while (i < j) {int t = Math.min(height[i], height[j]) * (j - i);ans = Math.max(ans, t);if (height[i] < height[j]) {++i;} else {--j;}}return ans;}
}

C++

class Solution {
public:int maxArea(vector<int>& height) {int i = 0, j = height.size() - 1;int ans = 0;while (i < j) {int t = min(height[i], height[j]) * (j - i);ans = max(ans, t);if (height[i] < height[j]) {++i;} else {--j;}}return ans;}
};

---

leetcode.cn/problems/integer-to-roman" rel="nofollow">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：

输出： "MMMDCCXLIX"

解释：

3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC 由于 500 (D) + 100 © + 100 ©
40 = XL 由于 50 (L) 减 10 (X)
9 = IX 由于 10 (X) 减 1 (I)
注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

示例 2：

输出："LVIII"

解释：

50 = L
8 = VIII

示例 3：

输出："MCMXCIV"

解释：

1000 = M
900 = CM
90 = XC
4 = IV

 

提示：

• 1 <= num <= 3999

难度：中等

标签：哈希表,数学,字符串

解法

方法一：贪心

我们可以先将所有可能的符号 $cs$ 和对应的数值 $vs$ 列出来，然后从大到小枚举每个数值 $vs[i]$，每次尽可能多地使用该数值对应的符号 $cs[i]$，直到数字 $num$ 变为 $0$。

时间复杂度为 $O(m)$，空间复杂度为 $O(m)$。其中 $m$ 为符号的个数。

Python3

class Solution:def intToRoman(self, num: int) -> str:cs = ('M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I')vs = (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)ans = []for c, v in zip(cs, vs):while num >= v:num -= vans.append(c)return ''.join(ans)

Java

class Solution {public String intToRoman(int num) {List<String> cs= List.of("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I");List<Integer> vs = List.of(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1);StringBuilder ans = new StringBuilder();for (int i = 0, n = cs.size(); i < n; ++i) {while (num >= vs.get(i)) {num -= vs.get(i);ans.append(cs.get(i));}}return ans.toString();}
}

C++

class Solution {
public:string intToRoman(int num) {vector<string> cs = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};vector<int> vs = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};string ans;for (int i = 0; i < cs.size(); ++i) {while (num >= vs[i]) {num -= vs[i];ans += cs[i];}}return ans;}
};

---

leetcode.cn/problems/roman-to-integer" rel="nofollow">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 <= 15
• s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
• 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
• 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
• IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
• 关于罗马数字的详尽书写规则，可以参考 罗马数字 - 百度百科。

难度：简单

标签：哈希表,数学,字符串

解法

方法一：哈希表 + 模拟

我们先用哈希表 $d$ 记录每个字符对应的数值，然后从左到右遍历字符串 $s$，如果当前字符对应的数值小于右边字符对应的数值，则减去当前字符对应的数值，否则加上当前字符对应的数值。

时间复杂度 $(n)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别为字符串 $s$ 的长度和字符集的大小。

Python3

class Solution:def romanToInt(self, s: str) -> int:d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}return sum((-1 if d[a] < d[b] else 1) * d[a] for a, b in pairwise(s)) + d[s[-1]]

Java

class Solution {public int romanToInt(String s) {String cs = "IVXLCDM";int[] vs = {1, 5, 10, 50, 100, 500, 1000};Map<Character, Integer> d = new HashMap<>();for (int i = 0; i < vs.length; ++i) {d.put(cs.charAt(i), vs[i]);}int n = s.length();int ans = d.get(s.charAt(n - 1));for (int i = 0; i < n - 1; ++i) {int sign = d.get(s.charAt(i)) < d.get(s.charAt(i + 1)) ? -1 : 1;ans += sign * d.get(s.charAt(i));}return ans;}
}

C++

class Solution {
public:int romanToInt(string s) {unordered_map<char, int> nums{{'I', 1},{'V', 5},{'X', 10},{'L', 50},{'C', 100},{'D', 500},{'M', 1000},};int ans = nums[s.back()];for (int i = 0; i < s.size() - 1; ++i) {int sign = nums[s[i]] < nums[s[i + 1]] ? -1 : 1;ans += sign * nums[s[i]];}return ans;}
};

---

leetcode.cn/problems/longest-common-prefix" rel="nofollow">14. 最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

 

示例 1：

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

示例 2：

输入：strs = [“dog”,“racecar”,“car”]
输出：“”
解释：输入不存在公共前缀。

 

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

难度：简单

标签：字典树,字符串

解法

方法一：字符比较

我们以第一个字符串 $strs[0]$ 为基准，依次比较后面的字符串的第 $i$ 个字符是否与 $strs[0]$ 的第 $i$ 个字符相同，如果相同则继续比较下一个字符，否则返回 $strs[0]$ 的前 $i$ 个字符。

遍历结束，说明所有字符串的前 $i$ 个字符都相同，返回 $strs[0]$ 即可。

时间复杂度 $(n\times m)$，其中 $n$ 和 $m$ 分别为字符串数组的长度以及字符串的最小长度。空间复杂度 $O(1)$。

Python3

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:for i in range(len(strs[0])):for s in strs[1:]:if len(s) <= i or s[i] != strs[0][i]:return s[:i]return strs[0]

Java

class Solution {public String longestCommonPrefix(String[] strs) {int n = strs.length;for (int i = 0; i < strs[0].length(); ++i) {for (int j = 1; j < n; ++j) {if (strs[j].length() <= i || strs[j].charAt(i) != strs[0].charAt(i)) {return strs[0].substring(0, i);}}}return strs[0];}
}

C++

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {int n = strs.size();for (int i = 0; i < strs[0].size(); ++i) {for (int j = 1; j < n; ++j) {if (strs[j].size() <= i || strs[j][i] != strs[0][i]) {return strs[0].substr(0, i);}}}return strs[0];}
};

---

leetcode.cn/problems/3sum" rel="nofollow">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

难度：中等

标签：数组,双指针,排序

解法

方法一：排序 + 双指针

我们注意到，题目不要求我们按照顺序返回三元组，因此我们不妨先对数组进行排序，这样就可以方便地跳过重复的元素。

接下来，我们枚举三元组的第一个元素 $nums[i]$，其中 $0\le i<n-2$。对于每个 $i$，我们可以通过维护两个指针 $j=i+1$ 和 $k=n-1$，从而找到满足 $nums[i]+nums[j]+nums[k]=0$ 的 $j$ 和 $k$。在枚举的过程中，我们需要跳过重复的元素，以避免出现重复的三元组。

具体判断逻辑如下：

如果 $i>0$ 并且 $nums[i]=nums[i-1]$，则说明当前枚举的元素与上一个元素相同，我们可以直接跳过，因为不会产生新的结果。

如果 $nums[i]>0$，则说明当前枚举的元素大于 $0$，则三数之和必然无法等于 $0$，结束枚举。

否则，我们令左指针 $j=i+1$，右指针 $k=n-1$，当 $j<k$ 时，执行循环，计算三数之和 $x=nums[i]+nums[j]+nums[k]$，并与 $0$ 比较：

• 如果 $x<0$，则说明 $nums[j]$ 太小，我们需要将 $j$ 右移一位。
• 如果 $x>0$，则说明 $nums[k]$ 太大，我们需要将 $k$ 左移一位。
• 否则，说明我们找到了一个合法的三元组，将其加入答案，并将 $j$ 右移一位，将 $k$ 左移一位，同时跳过所有重复的元素，继续寻找下一个合法的三元组。

枚举结束后，我们即可得到三元组的答案。

时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组的长度。

Python3

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()n = len(nums)ans = []for i in range(n - 2):if nums[i] > 0:breakif i and nums[i] == nums[i - 1]:continuej, k = i + 1, n - 1while j < k:x = nums[i] + nums[j] + nums[k]if x < 0:j += 1elif x > 0:k -= 1else:ans.append([nums[i], nums[j], nums[k]])j, k = j + 1, k - 1while j < k and nums[j] == nums[j - 1]:j += 1while j < k and nums[k] == nums[k + 1]:k -= 1return ans

Java

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<>();int n = nums.length;for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}int j = i + 1, k = n - 1;while (j < k) {int x = nums[i] + nums[j] + nums[k];if (x < 0) {++j;} else if (x > 0) {--k;} else {ans.add(List.of(nums[i], nums[j++], nums[k--]));while (j < k && nums[j] == nums[j - 1]) {++j;}while (j < k && nums[k] == nums[k + 1]) {--k;}}}}return ans;}
}

C++

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> ans;int n = nums.size();for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {if (i && nums[i] == nums[i - 1]) {continue;}int j = i + 1, k = n - 1;while (j < k) {int x = nums[i] + nums[j] + nums[k];if (x < 0) {++j;} else if (x > 0) {--k;} else {ans.push_back({nums[i], nums[j++], nums[k--]});while (j < k && nums[j] == nums[j - 1]) {++j;}while (j < k && nums[k] == nums[k + 1]) {--k;}}}}return ans;}
};

---

leetcode.cn/problems/3sum-closest" rel="nofollow">16. 最接近的三数之和

题目描述

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

 

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

 

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

难度：中等

标签：数组,双指针,排序

解法

方法一：排序 + 双指针

我们将数组排序，然后遍历数组，对于每个元素 $nums[i]$，我们使用指针 $j$ 和 $k$ 分别指向 $i+1$ 和 $n-1$，计算三数之和，如果三数之和等于 $target$，则直接返回 $target$，否则根据与 $target$ 的差值更新答案。如果三数之和大于 $target$，则将 $k$ 向左移动一位，否则将 $j$ 向右移动一位。

时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。

Python3

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:nums.sort()n = len(nums)ans = inffor i, v in enumerate(nums):j, k = i + 1, n - 1while j < k:t = v + nums[j] + nums[k]if t == target:return tif abs(t - target) < abs(ans - target):ans = tif t > target:k -= 1else:j += 1return ans

Java

class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int ans = 1 << 30;int n = nums.length;for (int i = 0; i < n; ++i) {int j = i + 1, k = n - 1;while (j < k) {int t = nums[i] + nums[j] + nums[k];if (t == target) {return t;}if (Math.abs(t - target) < Math.abs(ans - target)) {ans = t;}if (t > target) {--k;} else {++j;}}}return ans;}
}

C++

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int ans = 1 << 30;int n = nums.size();for (int i = 0; i < n; ++i) {int j = i + 1, k = n - 1;while (j < k) {int t = nums[i] + nums[j] + nums[k];if (t == target) return t;if (abs(t - target) < abs(ans - target)) ans = t;if (t > target)--k;else++j;}}return ans;}
};

---

leetcode.cn/problems/letter-combinations-of-a-phone-number" rel="nofollow">17. 电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

 

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：

输入：digits = “”
输出：[]

示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

 

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

难度：中等

标签：哈希表,字符串,回溯

解法

方法一：遍历

我们先用一个数组或者哈希表存储每个数字对应的字母，然后遍历每个数字，将其对应的字母与之前的结果进行组合，得到新的结果。

时间复杂度 $O(4^n)$。空间复杂度 $O(4^n)$。其中 $n$ 是输入数字的长度。

Python3

class Solution:def letterCombinations(self, digits: str) -> List[str]:if not digits:return []d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]ans = [""]for i in digits:s = d[int(i) - 2]ans = [a + b for a in ans for b in s]return ans

Java

class Solution {public List<String> letterCombinations(String digits) {List<String> ans = new ArrayList<>();if (digits.length() == 0) {return ans;}ans.add("");String[] d = new String[] {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};for (char i : digits.toCharArray()) {String s = d[i - '2'];List<String> t = new ArrayList<>();for (String a : ans) {for (String b : s.split("")) {t.add(a + b);}}ans = t;}return ans;}
}

C++

class Solution {
public:vector<string> letterCombinations(string digits) {if (digits.empty()) {return {};}vector<string> d = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};vector<string> ans = {""};for (auto& i : digits) {string s = d[i - '2'];vector<string> t;for (auto& a : ans) {for (auto& b : s) {t.push_back(a + b);}}ans = move(t);}return ans;}
};

---

leetcode.cn/problems/4sum" rel="nofollow">18. 四数之和

题目描述

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

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

 

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

难度：中等

标签：数组,双指针,排序

解法

方法一：排序 + 双指针

我们注意到，题目中要求找到不重复的四元组，那么我们可以先对数组进行排序，这样就可以方便地跳过重复的元素。

接下来，我们枚举四元组的前两个元素 $nums[i]$ 和 $nums[j]$，其中 $i<j$，在枚举的过程中，我们跳过重复的 $nums[i]$ 和 $nums[j]$。然后，我们用两个指针 $k$ 和 $l$ 分别指向 $nums[i]$ 和 $nums[j]$ 后面的两端，令 $x=nums[i]+nums[j]+nums[k]+nums[l]$，我们将 $x$ 与 $target$ 比较，进行如下操作：

• 如果 $x<target$，则更新 $k=k+1$ 以得到更大的 $x$；
• 如果 $x>target$，则更新 $l=l-1$ 以得到更小的 $x$；
• 否则，说明找到了一个四元组 $(nums[i],nums[j],nums[k],nums[l])$，将其加入答案，然后我们更新指针 $k$ 和 $l$，并跳过所有重复的元素，防止答案中包含重复的四元组，继续寻找下一个四元组。

时间复杂度为 $O(n^3)$，空间复杂度为 $O(\log n)$，其中 $n$ 是数组的长度。

Python3

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:n = len(nums)ans = []if n < 4:return ansnums.sort()for i in range(n - 3):if i and nums[i] == nums[i - 1]:continuefor j in range(i + 1, n - 2):if j > i + 1 and nums[j] == nums[j - 1]:continuek, l = j + 1, n - 1while k < l:x = nums[i] + nums[j] + nums[k] + nums[l]if x < target:k += 1elif x > target:l -= 1else:ans.append([nums[i], nums[j], nums[k], nums[l]])k, l = k + 1, l - 1while k < l and nums[k] == nums[k - 1]:k += 1while k < l and nums[l] == nums[l + 1]:l -= 1return ans

Java

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {int n = nums.length;List<List<Integer>> ans = new ArrayList<>();if (n < 4) {return ans;}Arrays.sort(nums);for (int i = 0; i < n - 3; ++i) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}for (int j = i + 1; j < n - 2; ++j) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}int k = j + 1, l = n - 1;while (k < l) {long x = (long) nums[i] + nums[j] + nums[k] + nums[l];if (x < target) {++k;} else if (x > target) {--l;} else {ans.add(List.of(nums[i], nums[j], nums[k++], nums[l--]));while (k < l && nums[k] == nums[k - 1]) {++k;}while (k < l && nums[l] == nums[l + 1]) {--l;}}}}}return ans;}
}

C++

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {int n = nums.size();vector<vector<int>> ans;if (n < 4) {return ans;}sort(nums.begin(), nums.end());for (int i = 0; i < n - 3; ++i) {if (i && nums[i] == nums[i - 1]) {continue;}for (int j = i + 1; j < n - 2; ++j) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}int k = j + 1, l = n - 1;while (k < l) {long long x = (long long) nums[i] + nums[j] + nums[k] + nums[l];if (x < target) {++k;} else if (x > target) {--l;} else {ans.push_back({nums[i], nums[j], nums[k++], nums[l--]});while (k < l && nums[k] == nums[k - 1]) {++k;}while (k < l && nums[l] == nums[l + 1]) {--l;}}}}}return ans;}
};

---

leetcode.cn/problems/remove-nth-node-from-end-of-list" rel="nofollow">19. 删除链表的倒数第 N 个结点

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

 

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

进阶：你能尝试使用一趟扫描实现吗？

难度：中等

标签：链表,双指针

解法

方法一：快慢指针

我们定义两个指针 fast 和 slow，初始时都指向链表的虚拟头结点 dummy。

接着 fast 指针先向前移动 $n$ 步，然后 fast 和 slow 指针同时向前移动，直到 fast 指针到达链表的末尾。此时 slow.next 指针指向的结点就是倒数第 n 个结点的前驱结点，将其删除即可。

时间复杂度 $O(n)$，其中 $n$ 为链表的长度。空间复杂度 $O(1)$。

Python3

## Definition for singly-linked list.
## class ListNode:
##     def __init__(self, val=0, next=None):
##         self.val = val
##         self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummy = ListNode(next=head)fast = slow = dummyfor _ in range(n):fast = fast.nextwhile fast.next:slow, fast = slow.next, fast.nextslow.next = slow.next.nextreturn dummy.next

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);ListNode fast = dummy, slow = dummy;while (n-- > 0) {fast = fast.next;}while (fast.next != null) {slow = slow.next;fast = fast.next;}slow.next = slow.next.next;return dummy.next;}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0, head);ListNode* fast = dummy;ListNode* slow = dummy;while (n--) {fast = fast->next;}while (fast->next) {slow = slow->next;fast = fast->next;}slow->next = slow->next->next;return dummy->next;}
};

---

leetcode.cn/problems/valid-parentheses" rel="nofollow">20. 有效的括号

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

 

示例 1：

输出：true

示例 2：

输出：true

示例 3：

输出：false

示例 4：

输出：true

 

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

难度：简单

标签：栈,字符串

解法

方法一：栈

遍历括号字符串 $s$，遇到左括号时，压入当前的左括号；遇到右括号时，弹出栈顶元素（若栈为空，直接返回 false），判断是否匹配，若不匹配，直接返回 false。

也可以选择遇到左括号时，将右括号压入栈中；遇到右括号时，弹出栈顶元素（若栈为空，直接返回 false），判断是否是相等。若不匹配，直接返回 false。

两者的区别仅限于括号转换时机，一个是在入栈时，一个是在出栈时。

遍历结束，若栈为空，说明括号字符串有效，返回 true；否则，返回 false。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为括号字符串 $s$ 的长度。

Python3

class Solution:def isValid(self, s: str) -> bool:stk = []d = {'()', '[]', '{}'}for c in s:if c in '({[':stk.append(c)elif not stk or stk.pop() + c not in d:return Falsereturn not stk

Java

class Solution {public boolean isValid(String s) {Deque<Character> stk = new ArrayDeque<>();for (char c : s.toCharArray()) {if (c == '(' || c == '{' || c == '[') {stk.push(c);} else if (stk.isEmpty() || !match(stk.pop(), c)) {return false;}}return stk.isEmpty();}private boolean match(char l, char r) {return (l == '(' && r == ')') || (l == '{' && r == '}') || (l == '[' && r == ']');}
}

C++

class Solution {
public:bool isValid(string s) {string stk;for (char c : s) {if (c == '(' || c == '{' || c == '[')stk.push_back(c);else if (stk.empty() || !match(stk.back(), c))return false;elsestk.pop_back();}return stk.empty();}bool match(char l, char r) {return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}');}
};

---