时间戳

首页 > 解决方案 > 尝试给出很长的字符串时，SubString 给出 OutOfMemory 异常

java - 尝试给出很长的字符串时，SubString 给出 OutOfMemory 异常

问题描述

我正在编写这段代码，以应对来自 leet 代码的编码挑战。

这段代码适用于 987 个测试用例中的 986 个。对于非常长的字符串（长度 ~ 31600）的情况，它会失败。子字符串函数抛出 java.lang.OutOfMemoryError: Java heap space。

我尝试创建“子字符串” new SubString(s.substring(i,j)); 和 s.substring(i,j).intern(); 在看到其他堆栈溢出的建议之后。但徒劳

private static Map<String, Integer> findAllSubStrings(String s) {
        Map<String, Integer> allSubStrings = new HashMap<>();
        for(int i = 0; i<s.length(); i++) {
            for(int j=i+1; j<=s.length(); j++) {
                String substring = s.substring(i,j);
                allSubStrings.put(substring, substring.length());
            }
        }
        return allSubStrings;
    }

例外是，

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.base/java.util.Arrays.copyOfRange(Arrays.java:4031)
at java.base/java.lang.StringLatin1.newString(StringLatin1.java:782)
at java.base/java.lang.String.substring(String.java:1888)
at main.LongestSubstring.findAllSubStrings(LongestSubstring.java:76)
at main.LongestSubstring.getLengthOfLongestSubString(LongestSubstring.java:44)
at main.LongestSubstring.main(LongestSubstring.java:38)

我正在寻找可以帮助我理解和解决此问题的人。

提前致谢。

标签： javastringsubstring

解决方案

正如例外所说，您的空间不足。

对于长度为的字符串，n需要n(n-1)/2创建不同的子字符串；当 n 大约为 32,000 时，这相当于大约 5亿个子字符串。每个String对象至少占用 16 个字节的堆（但可能更多，甚至假设它们都共享相同的底层char[]，这样我们就不需要单独计算内容），所以你需要至少 8 GB 来代表它们。您的默认 Java 堆限制可能没有那么大。

您需要回到绘图板并提出一种算法，该算法不依赖于同时存在于内存中的所有子字符串。

推荐阅读