简介
题目大概就是：给你一个只由'('或')'组成的括号字符串s，定义s的权值为最长合法子序列长度。例如字符串"(()()"的权值为4，最长合法子序列为"()()"。
输入：一个括号字符串，长度不超过200000。
输出：所有子串的权值和。
我的解决思路，双指针 + 统计左括号'('个数
代码片段
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String strInput = in.next();
char[] str = strInput.toCharArray();
int len = str.length;
long res = 0;
for (int left = 0; left < len; left++) {
int right = left;
int leftNum = str[right] == '(' ? 1 : 0;
long pre = 0;
long ans = pre;
while (right < len - 1) {
right++;
if (str[right] == '(') {
leftNum++;
} else {
if (leftNum != 0) {
pre += 2;
leftNum--;
}
}
ans += pre;
}
res += ans;
}
System.out.println(res);
}
}通过22%的测试用例，时间复杂度为O(n^2)，这是我能想到的最优方案的方法了，难道还有O(n)或O(nlogn)的方案吗？因为要求所有子串的权值和，最起码也得把所有子串都遍历到吧？做过的铁子们有更好的方案吗，可以评论区交流一下
评论 (1)
