算法刷题记录——LeetCode篇(1.4) [第31~40题](持续更新)

更新时间：2025-03-29

• 算法题解目录汇总：算法刷题记录——题解目录汇总
• 技术博客总目录：计算机技术系列博客——目录页

优先整理热门100及面试150，不定期持续更新，欢迎关注！

---

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：

输入：s = "(()"
输出：2

解释：最长有效括号子串是 “()”

示例 2：

输入：s = ")()())"
输出：4

解释：最长有效括号子串是 “()()”

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 10^4
• s[i] 为 '(' 或 ')'

---

方法一：动态规划

使用动态规划数组 dp，其中 dp[i] 表示以第 i 个字符结尾的最长有效括号子串的长度。通过分类讨论当前字符为 ) 时的两种情况，逐步填充 dp 数组并更新最大值。

1. 直接匹配：当前字符为 ) 且前一字符为 ( 时，直接形成有效括号对。
2. 嵌套匹配：当前字符为 ) 且前一字符也为 ) 时，向前回溯找到可能的匹配位置，并累加之前有效括号的长度。

代码实现(Java)：

class Solution {public int longestValidParentheses(String s) {int n = s.length();if (n == 0) return 0;int[] dp = new int[n]; // dp[i] 表示以i结尾的最长有效括号长度int maxLen = 0;for (int i = 1; i < n; i++) {if (s.charAt(i) == ')') {// 情况1：直接匹配前一个 '('if (s.charAt(i-1) == '(') {dp[i] = 2;if (i >= 2) {dp[i] += dp[i-2]; // 合并前序有效括号}}// 情况2：嵌套匹配，如 "(()())"else if (i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '(') {int prevLen = dp[i-1];int j = i - prevLen - 1; // 找到匹配的 '(' 位置dp[i] = prevLen + 2;if (j > 0) {dp[i] += dp[j-1]; // 合并j之前可能的有效括号}}maxLen = Math.max(maxLen, dp[i]);}// 当前字符为 '(' 时，dp[i] 默认为0，无需处理}return maxLen;}
}

复杂度分析

• 时间复杂度：O(n)，遍历字符串一次。
• 空间复杂度：O(n)，动态规划数组的空间开销。

---

方法二：栈

核心思想：
利用 栈 来跟踪未匹配括号的索引位置。栈底始终保持最近一个无法匹配的右括号的位置（初始为-1作为基准点），遇到左括号则压入索引，遇到右括号则弹出栈顶元素并计算当前有效子串长度。

关键点：

1. 栈初始化：压入-1作为基准点，处理边界情况。
2. 左括号处理：压入当前索引。
3. 右括号处理：弹出栈顶元素，若栈空则压入当前索引作为新基准，否则计算长度。

代码实现(Java)：

class Solution {public int longestValidParentheses(String s) {int maxLen = 0;Deque<Integer> stack = new ArrayDeque<>();stack.push(-1); // 初始基准点for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '(') {stack.push(i); // 左括号压入索引} else {stack.pop();   // 弹出栈顶（可能是匹配的左括号或基准点）if (stack.isEmpty()) {stack.push(i); // 栈空时更新基准点} else {// 计算当前有效长度并更新最大值maxLen = Math.max(maxLen, i - stack.peek());}}}return maxLen;}
}

复杂度分析

• 时间复杂度：O(n)，仅遍历字符串一次。
• 空间复杂度：O(n)，栈最多存储 n+1 个元素（如全左括号）。

---

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

---

方法：二分查找法

通过判断有序区间来缩小搜索范围，利用旋转数组的局部有序特性进行二分查找。

1. 确定有序区间：通过比较nums[left]和nums[mid]判断左半部分是否有序；
2. 区间范围检查：
   • 左半有序时，若目标值在[nums[left], nums[mid])区间内，则继续搜索左半；
   • 右半有序时，若目标值在(nums[mid], nums[right]]区间内，则继续搜索右半；
3. 动态调整边界：根据目标值所在区间动态调整左右指针，逐步缩小搜索范围。

代码实现(Java)：

class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;}// 判断左半部分是否有序if (nums[left] <= nums[mid]) {// 目标在有序的左半部分区间内if (target >= nums[left] && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}} else { // 右半部分有序// 目标在有序的右半部分区间内if (target > nums[mid] && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}return -1;}
}

时间复杂度分析：

• 每次循环将搜索范围减半，时间复杂度为O(log n) 。

---

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一个非递减数组
• -10^9 <= target <= 10^9

---

方法一：两次二分查找分别确定左右边界

通过两次独立的二分查找分别定位目标值的起始和结束位置，时间复杂度保持O(log n)。

1. 左边界查找：当中间值>=目标时收缩右边界，最终左指针指向第一个目标值位置；
2. 右边界查找：当中间值<=目标时收缩左边界，最终右指针指向最后一个目标值位置；
3. 边界校验：两次查找后均进行有效性验证，确保找到的是真实的目标值位置。

代码实现(Java)：

class Solution {public int[] searchRange(int[] nums, int target) {int[] result = {-1, -1};if (nums == null || nums.length == 0) return result;// 寻找左边界int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}if (left >= nums.length || nums[left] != target) return result;result[0] = left;// 寻找右边界right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;} else {right = mid - 1;}}result[1] = right;return result;}
}

---

方法二：单次二分配合线性扫描（不推荐）

代码实现(Java)：

class Solution {public int[] searchRange(int[] nums, int target) {int[] result = {-1, -1};if (nums.length == 0) return result;int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left)/2;if (nums[mid] == target) {// 向两侧扩展int l = mid, r = mid;while (l >= 0 && nums[l] == target) l--;while (r < nums.length && nums[r] == target) r++;return new int[]{l+1, r-1};} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return result;}
}

---

复杂度分析

方法	时间复杂度	空间复杂度	特点
方法一	O(log n)	O(1)	严格满足题目要求
方法二	O(n)	O(1)	最坏情况效率低，仅作参考

---

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 为 无重复元素 的 升序 排列数组
• -10^4 <= target <= 10^4

---

方法一：标准二分查找

通过常规二分查找确定目标值位置，未找到时返回左指针即为插入位置。

1. 循环查找：当左指针不超过右指针时持续查找；
2. 三种情况处理：
   • 找到相等元素直接返回索引；
   • 中间值小于目标时收缩左边界；
   • 中间值大于目标时收缩右边界；
3. 终止条件：未找到时左指针即为插入位置。

代码实现(Java)：

class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;}
}

---

方法二：左闭右开区间优化

直接寻找第一个大于等于目标的位置，统一处理存在/不存在两种情况。

代码实现(Java)：

class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid;} else {left = mid + 1;}}return left;}
}

复杂度分析

方法	时间复杂度	空间复杂度	特点
方法一	O(log n)	O(1)	直观易理解，立即返回命中
方法二	O(log n)	O(1)	代码更简洁，统一处理逻辑

---

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

---

方法一：回溯法（剪枝优化）

通过排序和剪枝策略减少无效搜索，每次递归从当前索引开始允许重复选取元素。

代码实现(Java)：

public class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(candidates); // 排序用于剪枝backtrack(res, new ArrayList<>(), candidates, target, 0, 0);return res;}private void backtrack(List<List<Integer>> res, List<Integer> path,int[] candidates, int target, int sum, int start) {if (sum == target) {res.add(new ArrayList<>(path));return;}for (int i = start; i < candidates.length; i++) {int num = candidates[i];if (sum + num > target) break; // 剪枝：后续元素更大无需遍历path.add(num);backtrack(res, path, candidates, target, sum + num, i); // 允许重复选当前元素path.remove(path.size() - 1);}}
}

时间复杂度： O(2^n)（实际远小于，剪枝显著减少搜索空间）
空间复杂度： O(target/min(candidates)) 递归栈深度与路径长度相关

---

方法二：动态规划（扩展思路）

使用动态规划记录所有可能的组合，适用于小规模目标值。

代码实现(Java)：

public class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);List<List<Integer>>[] dp = new ArrayList[target + 1];dp[0] = new ArrayList<>();dp[0].add(new ArrayList<>());for (int t = 1; t <= target; t++) {dp[t] = new ArrayList<>();for (int num : candidates) {if (num > t) break;for (List<Integer> prev : dp[t - num]) {if (!prev.isEmpty() && prev.get(prev.size()-1) > num) continue;List<Integer> temp = new ArrayList<>(prev);temp.add(num);dp[t].add(temp);}}}return dp[target];}
}

时间复杂度： O(n * target * k)（k为组合数，效率低于回溯法）。
空间复杂度： O(target * k) 存储所有中间组合。

---

方法三：迭代法（BFS队列）

通过队列实现广度优先搜索，逐步构建所有有效组合。

代码实现(Java)：

public class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);Queue<Node> queue = new ArrayDeque<>();queue.offer(new Node(0, new ArrayList<>(), 0));List<List<Integer>> res = new ArrayList<>();while (!queue.isEmpty()) {Node cur = queue.poll();if (cur.sum == target) {res.add(cur.path);continue;}for (int i = cur.start; i < candidates.length; i++) {int newSum = cur.sum + candidates[i];if (newSum > target) break;List<Integer> newPath = new ArrayList<>(cur.path);newPath.add(candidates[i]);queue.offer(new Node(newSum, newPath, i));}}return res;}static class Node {int sum;List<Integer> path;int start;public Node(int sum, List<Integer> path, int start) {this.sum = sum;this.path = path;this.start = start;}}
}

时间复杂度： O(2^n)，与回溯法相同。
空间复杂度： O(k)，队列存储中间状态。

---

声明

1. 本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵循CC-BY-SA协议发布，转载请注明出处。
2. 本文题目来源 力扣-LeetCode ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。