小编ana*_*ala的帖子

这段代码来自Cracking the Coding访谈书.

public static boolean isUniqueChars2(String str) {
    boolean[] char_set = new boolean[256];
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (char_set[val]) return false;
        char_set[val] = true;
    }
    return true;
}

作者提到,

时间复杂度为O(n),其中n是字符串的长度,空间复杂度为O(n).

我理解时间复杂度为O(n)但我不明白空间复杂度怎么可能是O(n)

我的想法:无论输入(str)大小是多少,char_set都将保持256大小的数组.即使"str"的长度为100,000,char_set仍然是256个元素的数组.所以我想,因为这个函数的内存需求不随输入的大小而变化并保持常数256,所以空间复杂度是常数,即O(1).

有人可以解释,如果我错了(为什么？)

非常感谢.