两道经典算法题：分割等和子集 最长有效括号 详解

目录一、分割等和子集中等难度题目描述核心思路分析代码实现Java复杂度分析二、最长有效括号困难难度题目描述核心思路分析代码实现Java复杂度分析三、两道题的对比与总结这两道题分别是「动态规划」和「栈 / 动态规划」的经典代表一个中等难度、一个困难难度刚好能帮你夯实算法基础。下面我会用通俗易懂的方式把思路、代码和优化都讲明白直接可以当成博客内容发布。一、分割等和子集中等难度题目描述给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。核心思路分析这道题本质上是0-1 背包问题的变形首先计算数组的总和total如果total是奇数直接返回false不可能分成两个和相等的子集。目标转化为从数组中选出一些数它们的和等于total / 2。用动态规划解决定义dp[i]表示是否能选出和为i的子集。初始状态dp[0] true和为 0 的子集总是存在即空集。遍历数组中的每个数num然后从后往前更新dp数组dp[j] dp[j] || dp[j - num]。代码实现Javajava运行public class CanPartition { public boolean canPartition(int[] nums) { int totalSum 0; for (int num : nums) { totalSum num; } // 总和为奇数直接返回false if (totalSum % 2 ! 0) { return false; } int target totalSum / 2; boolean[] dp new boolean[target 1]; dp[0] true; for (int num : nums) { // 从后往前遍历避免重复使用同一个元素 for (int j target; j num; j--) { dp[j] dp[j] || dp[j - num]; } } return dp[target]; } }复杂度分析时间复杂度O(n * target)n是数组长度target是总和的一半。空间复杂度O(target)使用一维数组优化了空间。二、最长有效括号困难难度题目描述给你一个只包含(和)的字符串找出最长有效格式正确且连续括号子串的长度。核心思路分析这道题有两种主流解法栈和动态规划这里我们用栈来实现思路更直观。栈的核心思想栈中存储的是括号的索引初始时放入-1作为 “哨兵”方便计算长度。遇到(将当前索引入栈。遇到)弹出栈顶元素。如果栈为空说明当前)无法匹配将当前索引入栈作为新的哨兵。如果栈不为空当前索引减去栈顶元素就是当前有效括号的长度更新最大值。代码实现Javajava运行import java.util.Stack; public class LongestValidParentheses { public int longestValidParentheses(String s) { StackInteger stack new Stack(); // 哨兵元素用于计算长度 stack.push(-1); int maxLen 0; 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)n是字符串长度每个字符入栈和出栈各一次。空间复杂度O(n)最坏情况下栈需要存储所有索引比如全是(。三、两道题的对比与总结表格题目核心算法关键难点适用场景分割等和子集动态规划0-1 背包问题转化、一维 DP 优化子集和问题、资源分配问题最长有效括号栈 / 动态规划哨兵的使用、边界处理括号匹配、字符串处理问题这两道题都是算法面试中的高频考点它们分别代表了动态规划和栈两种经典解题思路分割等和子集教会你如何把 “子集和” 问题转化为背包模型并用一维数组优化空间。最长有效括号则展示了栈在处理 “匹配类” 问题时的强大能力尤其是哨兵技巧的妙用。