18. 四数之和，19. 删除链表的倒数第 N 个结点，20. 有效的括号 ，每题做详细思路梳理，配套Python&Java双语代码， 2024.03.12 可通过leetcode所有测试用例。
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]]
解题思路
可以通过使用双指针法加上两层循环的方式来解决，主要步骤如下：
-
排序：首先对数组进行排序，这样可以方便后续去重以及使用双指针法。
-
遍历：使用两层循环遍历数组，第一层循环枚举第一个数，第二层循环枚举第二个数。
-
双指针：在每一对固定的第一和第二个数后，使用两个指针分别指向剩余部分的开始和结束位置，移动指针寻找满足条件的四元组。
-
去重：在遍历和双指针移动的过程中，需要注意去重。
完整代码
Python
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left, right = j + 1, n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total < target:
left += 1
elif total > target:
right -= 1
else:
res.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return resJava
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1, right = n - 1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
}
return res;
}
}
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
解题思路
删除链表的倒数第n个节点可以通过一次遍历完成，主要思路是使用两个指针：快指针和慢指针。首先让快指针向前移动n步，然后快慢指针同时移动，直到快指针指向链表末尾。此时，慢指针的下一个节点就是需要删除的节点。具体步骤如下：
-
创建一个哑结点：哑结点指向链表的头部，这样做的好处是可以简化对头结点进行操作的复杂度，尤其是当头结点需要被删除时。
-
初始化快慢指针：快慢指针都指向哑结点。
-
移动快指针：快指针向前移动n+1步，这样快慢指针之间就保持了n个节点的距离。
-
同时移动快慢指针：快慢指针同时向前移动，直到快指针指向链表末尾的null。
-
删除节点：此时慢指针的下一个节点就是需要删除的节点，通过修改慢指针的next指针来跳过这个节点。
完整代码
Python
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
fast = slow = dummy
# 快指针先前移n+1步
for _ in range(n + 1):
fast = fast.next
# 快慢指针同时移动直到快指针到达末尾
while fast:
fast = fast.next
slow = slow.next
# 删除倒数第n个节点
slow.next = slow.next.next
return dummy.nextJava
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
// 快指针先前移n+1步
for (int i = 1; i <= n + 1; i++) {
fast = fast.next;
}
// 快慢指针同时移动直到快指针到达末尾
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// 删除倒数第n个节点
slow.next = slow.next.next;
return dummy.next;
}
}
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：输入：s = "()[]{}"
输出：true
示例 3：输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
解题思路
判断括号字符串是否有效的一个常用方法是使用栈。基本思想是遍历字符串，每次遇到一个左括号就将其推入栈中，每次遇到一个右括号就检查栈顶元素是否为对应的左括号，如果是，则将栈顶元素弹出；如果不是或栈为空，则说明字符串无效。遍历结束后，如果栈为空，则说明所有括号都正确匹配，字符串有效；如果栈不为空，则说明有未匹配的左括号，字符串无效。
完整代码
Python
class Solution:
def isValid(self, s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stackJava
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> mapping = new HashMap<>();
mapping.put(')', '(');
mapping.put('}', '{');
mapping.put(']', '[');
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (mapping.containsKey(c)) {
char topElement = stack.isEmpty() ? '#' : stack.pop();
if (mapping.get(c) != topElement) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
