Java的repeatedString方法传大数值n报int字面量超出范围如何解决

问题原因 #

• 类型溢出错误：Java中int类型的取值范围仅为-2^31 ~ 2^31-1（即-2147483648 ~ 2147483647），你代码中直接将long类型的参数n强转为int，当n为1000000000000这类远大于int上限的数值时，强转操作直接触发范围溢出错误。
• 实现逻辑本身不合理：即便没有类型溢出问题，直接创建长度等于n的字符串的思路也不可行，当n达到1e12级别时，对应字符串会占用TB级的内存空间，直接会导致内存溢出，完全没有实际运行的可能性。

解决方案 #

不需要生成完整的重复字符串，通过数学计算即可得到结果：

1. 先统计单个原字符串s中字符a的出现次数
2. 计算字符串s完整重复的次数：n / s.length()，乘以单个字符串的a数量得到完整重复部分的总a数
3. 计算剩下不足一个完整字符串的余数长度：n % s.length()，统计原字符串前余数个字符中的a数量
4. 两部分结果相加就是最终的总a数量

修正后的代码如下：

public static long repeatedString(String s, long n) {
    int strLen = s.length();
    // 统计单个字符串里的a数量
    long countPerStr = 0;
    for (char c : s.toCharArray()) {
        if (c == 'a') {
            countPerStr++;
        }
    }
    // 完整重复次数
    long fullTimes = n / strLen;
    // 剩余字符长度
    long remainder = n % strLen;
    // 统计剩余部分的a数量
    long countRemain = 0;
    for (int i = 0; i < remainder; i++) {
        if (s.charAt(i) == 'a') {
            countRemain++;
        }
    }
    long total = fullTimes * countPerStr + countRemain;
    System.out.println(total);
    return total;
}

该实现的时间复杂度仅为O(len(s))，不管n的数值多大都可以正常运行，不会出现内存溢出或类型溢出问题。

内容的提问来源于stack exchange，提问作者Hispalis Guadal