为什么不是o（n^3），因为在每个for循环中，我们做2个循环，一个用于len1，另一个用于len2？
下面的解决方案是正确输出回文。但我很困惑。
以下是leetcode的解决方案：
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
//Loop 1
for (int i = 0; i < s.length(); i++) {
//Loop 2
int len1 = expandAroundCenter(s, i, i);
//Loop 3
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}你知道吗？
2条答案
按热度按时间368yc8dk1#
你可能会被
expandAroundCenter跑两次。expandAroundCenter函数为o（n）。它运行了两次，但是，它是按顺序运行的。所以它类似于o（2n），而不是o（n^2）。当在for循环中调用expandaroundcenter函数时：
T(n) = n x 2n = 2n^2所以，时间复杂度是o（n^2）。eblbsuwk2#
论点很直截了当：
外环是
∈ O(n)两个内部循环（调用expandAroundCenter(...))按顺序运行，而不是嵌套运行。因此，它们的复杂性可以加起来对于内部循环，最坏的情况是它从循环的中心扩展
String向外，即。left以及right设置为n/2. 在这种情况下，内部循环最多可以迭代n/2-从那以后的几次left < 0或者right >= n. 因此，总的来说，内部循环是∈ O(n)总的来说，我们得到了O(n) (outer loop) * 2 * O(n) (inner loops in sequence) ∈ O(n^2)关于代码的一些注解：虽然可能，但在java中，在一行中声明多个变量是不常见的。因此
应该是
此更改只是代码样式的选择，对字节码没有影响。详见此帖。
单行语句周围的可选大括号绝对不能省略。如果我们以后想添加一行而忘记包含所需的大括号，那么这可能是一个令人讨厌的bug的来源。因此
应重新写入
变量名应该以小写字母开头(
L->l,R->r).变量应该有有意义的名称。
l以及r不是很有意义。因此，我建议进行以下重构：重命名参数
left以及right至leftStart以及rightStart重命名参数l以及r至currentLeft以及currentRight