问答

当前位置

时间复杂度

  • Ta: 马克助教

Longest Substring Without Repeating Characters 这道题的答案的时间复杂度是O(n) 还是 O(n * 2)?一个ForLoop里面套一个可能递增到String长度whileLoop应该是n * 2吧?
public int lengthOfLongestSubstring(String s) {
int[] map = new int[256]; // map from character's ASCII to its last occured index

    int j = 0;
    int i = 0;
    int ans = 0;
    for (i = 0; i < s.length(); i++) {
        while (j < s.length() && map[s.charAt(j)]==0) {
            map[s.charAt(j)] = 1;
            ans = Math.max(ans, j-i + 1);
            j ++;
        }
        map[s.charAt(i)] = 0;
    }

    return ans;
}

2 个回复

2017-12-27 安助教

这是双指针题型的题目之一,时间复杂度均为O(n),在分析时间复杂度的过程中,一般取增长速度最快的一项,且忽略这一项之前的常数。


2017-12-27 斌助教

这里的i,j相当于是双指针,i和j都只会遍历s.length,所以整体的复杂度为O(n),O(n * 2)也是O(n)。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1