向字符串添加空格算法调优

Question

问题链接是

力扣 https://leetcode-cn.com/contest/weekly-contest-272/problems/adding-spaces-to-a-string/

我写的代码

class Solution {
    public String addSpaces(String s, int[] spaces) {
        StringBuilder stringBuilder = new StringBuilder(s);
        int c = 0;
        for (int v : spaces) {
            stringBuilder.insert(v + c++, ' ');
        }
        return stringBuilder.toString();
    }
}

但是不知道为什么性能很差，不是说频繁的字符串拼接用StringBuilder性能好吗？

我现在的方案怎么优化呢

Answer 1

StringBuilder 的 insert 复杂度是 n，所以你每次插入都要遍历一次 整个 StringBuilder 字符串

性能并不如你想象的好。建议改用 StringBuilder 的 append 方法

public String addSpaces(String s, int[] spaces) {
    StringBuilder stringBuilder = new StringBuilder();
    int p1 = 0, p2 = 0, len = s.length(), n = spaces.length;
    while (p1 < len) {
        if (p2 < n && p1 == spaces[p2]) {
            stringBuilder.append(' ');
            p2++;
        }
        stringBuilder.append(s.charAt(p1++));
    }
    while (p2++ < n) {
        stringBuilder.append(' ');
    }
    return stringBuilder.toString();
}

我提交了下测试结果为