[算法] 字符串 – 初步与优化

连续子串去重

保留连续重复子串中首个子串，其余去重，输入输出均为数组

① 串右移并与自身逐位比较，逐次删除一位、两位、三位…的重复子串
若串右移i位后与自身重合i位（即靠前的子串与相邻靠后的子串匹配上），则说明这i位为连续重复子串，删除匹配部分即可
感谢@Andy Wang

public static int[] filter(int[] nums) {
    List<Integer> src = new ArrayList<>();
    List<Integer> win = src;
    for (int i = 0; i < nums.length; i++)
        src.add(nums[i]);

    for (int i = 1; i <= src.size() / 2; i++) {
        List<Integer> flag = new ArrayList<>();
        for (int j = 0; j < i; j++) flag.add(0);

        for (int j = i, k = 0; j < src.size(); j++, k++) {
            if (win.get(k).equals(src.get(j))) flag.add(1);
            else flag.add(0);
        }

        int sum = 0;
        for (int m = flag.size() - 1; m >= 0; m--) {
            if (flag.get(m).equals(1)) sum++;
            else sum = 0;
            if (sum == i) {
                int first = m;
                int last = m + sum - 1;
                for (int t = last; t >= first; t--)
                    src.remove(t);
                sum = 0;
            }
        }
    }
    return src.stream().mapToInt(Integer::valueOf).toArray();
}

详细说明

win与src比较，即src[当前位 + 右移位]与src[当前位]比较
倒序删除匹配项，无需考虑正序删除的下标问题
删除匹配项后src规模减小，进一步提升效率

右移1位 = 连续重合1位，存在单个元素组成的连续重复子串，删除匹配项

    i    1
    flag [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    src  [1, 2, 4, 1, 2, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6]
    win  [0, 1, 2, 4, 1, 2, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6, 2, 3, 2, 5]

右移2位 ≠ 连续重合1位，无连续重复子串匹配

    i    2
    flag [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0]
    src  [1, 2, 4, 1, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6]
    win  [0, 0, 1, 2, 4, 1, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6, 2, 3, 2]

同上，连续重合位数 ≠ 右移位数

    i    3
    flag [0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0]
    src  [1, 2, 4, 1, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6]
    win  [0, 0, 0, 1, 2, 4, 1, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6, 2, 3]

无匹配

    i    4
    flag [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    src  [1, 2, 4, 1, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6]
    win  [0, 0, 0, 0, 1, 2, 4, 1, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6, 2]

右移5位后，两次连续匹配5位，此处有5个元素组成的连续重复子串，需要删除两轮

    i    5
    flag [0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    src  [1, 2, 4, 1, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6]
    win  [0, 0, 0, 0, 0, 1, 2, 4, 1, 2, 3, 2, 5, 6, 2, 3, 2, 5, 6]

最长连续重复子串长度不会超过现在串长度的一半src.size() / 2，跳出循环

    src  [1, 2, 4, 1, 2, 3, 2, 5, 6]

# 样例
输入 [1, 2, 3, 2, 4, 1, 2, 3, 2, 3]
输出 [1, 2, 3, 2, 4, 1, 2, 3]

输入 [1, 2, 3, 2, 4, 1, 2, 3, 2, 3, 1, 2, 3, 2, 3]
输出 [1, 2, 3, 2, 4, 1, 2, 3]

输入 [1, 2, 3, 2, 3, 1, 2, 3, 2, 3]
输出 [1, 2, 3]

输入 [1, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3]
输出 [1, 2, 3]

输入 [1, 2, 3, 4, 5, 2, 3, 4, 5, 2, 3, 4, 5, 2, 3, 4, 5]
输出 [1, 2, 3, 4, 5]

输入 [1, 2, 3, 4, 2, 3, 4, 5]
输出 [1, 2, 3, 4, 5]

输入 [1, 1, 1, 1, 1, 1, 1]
输出 [1]

输入 [1, 2, 2, 2, 3, 4, 5]
输出 [1, 2, 3, 4, 5]

输入 [1, 2, 3, 4, 5, 2, 3, 4, 1]
输出 [1, 2, 3, 4, 5, 2, 3, 4, 1]

输入 [1, 2, 3, 4, 5, 1, 2, 3, 4]
输出 [1, 2, 3, 4, 5, 1, 2, 3, 4]

输入 [1, 2, 3, 2, 3, 1, 4, 2, 5, 1, 2, 3, 2, 3, 1, 4, 2, 5]
输出 [1, 2, 3, 1, 4, 2, 5]

输入 [1, 2, 3, 2, 3, 1, 4, 2, 5, 1, 2, 3, 1, 4, 2, 5]
输出 [1, 2, 3, 1, 4, 2, 5]

输入 [1, 2, 3, 2, 3, 1, 4, 2, 5, 1, 2, 3, 2, 3, 2, 3, 1, 4, 2, 5]
输出 [1, 2, 3, 1, 4, 2, 5]

输入 [1, 2, 3, 2, 3, 1, 4, 2, 5, 1, 2, 3, 2, 3, 2, 3, 1, 4, 2, 5, 1, 2, 3, 2, 3, 2, 3, 2, 3, 1, 4, 2, 5]
输出 [1, 2, 3, 1, 4, 2, 5]