shelterofly

目标

我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的有序列表（从小到大排序）。

示例 1：

输出：low = 100, high = 300
输出：[123,234]

示例 2：

输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]

说明：

10 <= low <= high <= 10^9

思路

定义顺序数字为从左到右每一位都比前一位的数字大 1 的整数。返回 [low, high] 范围内的所有顺序数字，按从小到大返回。

枚举数字长度以及开头数字，判断生成的顺序数字是否在 [low, high] 内即可。

代码


/**
 * @date 2026-07-13 9:10
 */
public class SequentialDigits1291 {

    public List<Integer> sequentialDigits(int low, int high) {
        int l = Integer.toString(low).length();
        int r = Integer.toString(high).length();
        List<Integer> res = new ArrayList<>();
        for (int i = l; i <= r; i++) {
            for(int j = 1; j + i <= 10; j++){
                Integer num = genInteger(j, i);
                if (low <= num && num <= high){
                    res.add(num);
                }
            }
        }
        return res;
    }

    public Integer genInteger(int first, int length) {
        int res = 0;
        for (int i = 0; i < length && first < 10; i++) {
            res = res * 10 + first;
            first++;
        }
        return res;
    }

}

性能

目标

给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。

序号代表了一个元素有多大。序号编号的规则如下：

序号从 1 开始编号。
一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
每个数字的序号都应该尽可能地小。

示例 1：

输入：arr = [40,10,20,30]
输出：[4,1,2,3]
解释：40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。

示例 2：

输入：arr = [100,100,100]
输出：[1,1,1]
解释：所有元素有相同的序号。

示例 3：

输入：arr = [37,12,28,9,100,56,80,5,12]
输出：[5,3,4,2,8,6,7,1,3]

说明：

0 <= arr.length <= 10^5
-10^9 <= arr[i] <= 10^9

思路

有一个整数数组 arr，返回每个元素排序后的序号，序号从 1 开始，如果元素值相同那么序号也相同，并且后面的序号无需考虑前面重复的元素，比如 [10 20 20 30]，返回 [1, 2, 2, 3] 而不是 [1, 2, 2, 4]。

排序 arr 的下标数组 index，根据排序后的 index 返填原数组的序号，注意去重即可。

代码


/**
 * @date 2026-07-14 10:11
 */
public class ArrayRankTransform1331 {

    public int[] arrayRankTransform(int[] arr) {
        int n = arr.length;
        Integer[] index = new Integer[n];
        Arrays.setAll(index, i -> i);
        Arrays.sort(index, (a, b) -> (arr[a] - arr[b]));
        int prev = Integer.MIN_VALUE;
        int sort = 0;
        for (int i = 0; i < n; i++) {
            if (prev != arr[index[i]]){
                sort++;
            }
            prev = arr[index[i]];
            arr[index[i]] = sort;
        }
        return arr;
    }

}

性能

目标

给你一个整数 n 。现有一个包含 n 个顶点的无向图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条无向边。

返回图中完全连通分量的数量。

如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为连通分量。

如果连通分量中每对节点之间都存在一条边，则称其为完全连通分量。

示例 1：

输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
输出：3
解释：如上图所示，可以看到此图所有分量都是完全连通分量。

示例 2：

输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
输出：1
解释：包含节点 0、1 和 2 的分量是完全连通分量，因为每对节点之间都存在一条边。
包含节点 3 、4 和 5 的分量不是完全连通分量，因为节点 4 和 5 之间不存在边。
因此，在图中完全连接分量的数量是 1 。

说明：

1 <= n <= 50
0 <= edges.length <= n * (n - 1) / 2
edges[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
不存在重复的边

思路

求无向图中完全连通分量的个数。完全连通分量指连通分量中任意两个节点之间都有一条边。

暴力解法是使用并查集维护连通分量，找出同一连通分量内的节点，判断两两之间是否有边。

优化点：可以利用节点与边的关系来判断是否是完全连通分量，节点 v 与边 e 的关系为：e = C(v, 2) = v * (v - 1) / 2。

代码


/**
 * @date 2026-07-14 11:27
 */
public class CountCompleteComponents2685 {

    private class UnionFind {

        private final int[] fa;

        public UnionFind(int n) {
            fa = new int[n];
            Arrays.setAll(fa, i -> i);
        }

        public int find(int e) {
            if (e != fa[e]) {
                fa[e] = find(fa[e]);
            }
            return fa[e];
        }

        public void union(int a, int b) {
            int x = find(a);
            int y = find(b);
            if (x > y) {
                fa[x] = y;
            } else {
                fa[y] = x;
            }
        }

        public int getCompleteComponents(Set<Integer>[] g) {
            int n = fa.length;
            int res = 0;
            Set<Integer> visited = new HashSet<>();
            for (int i = 0; i < n; i++) {
                if (visited.contains(i)) {
                    continue;
                }
                visited.add(i);
                List<Integer> list = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    if (find(j) == find(i)) {
                        visited.add(j);
                        list.add(j);
                    }
                }
                int size = list.size();
                boolean flag = true;
                here:
                for (int p = 0; p < size; p++) {
                    for (int q = p + 1; q < size; q++) {
                        if (!g[list.get(p)].contains(list.get(q))) {
                            flag = false;
                            break here;
                        }
                    }
                }
                if (flag) {
                    res++;
                }
            }
            return res;
        }
    }

    public int countCompleteComponents(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        Set<Integer>[] g = new HashSet[n];
        Arrays.setAll(g, x -> new HashSet<>());
        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            uf.union(a, b);
            g[a].add(b);
            g[b].add(a);
        }
        return uf.getCompleteComponents(g);
    }

}

性能

目标

给你一个整数 n，表示图中的节点数量，这些节点按从 0 到 n - 1 编号。

同时给你一个长度为 n 的整数数组 nums，该数组按非递减顺序排序，以及一个整数 maxDiff。

如果满足 |nums[i] - nums[j]| <= maxDiff（即 nums[i] 和 nums[j] 的绝对差至多为 maxDiff），则节点 i 和节点 j 之间存在一条无向边。

此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，需要判断节点 ui 和 vi 之间是否存在路径。

返回一个布尔数组 answer，其中 answer[i] 等于 true 表示在第 i 个查询中节点 ui 和 vi 之间存在路径，否则为 false。

示例 1：

输入: n = 2, nums = [1,3], maxDiff = 1, queries = [[0,0],[0,1]]
输出: [true,false]
解释:
查询 [0,0]：节点 0 有一条到自己的显然路径。
查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |1 - 3| = 2，大于 maxDiff。
因此，在处理完所有查询后，最终答案为 [true, false]。

示例 2：

输入: n = 4, nums = [2,5,6,8], maxDiff = 2, queries = [[0,1],[0,2],[1,3],[2,3]]
输出: [false,false,true,true]
解释:
生成的图如下：
查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |2 - 5| = 3，大于 maxDiff。
查询 [0,2]：节点 0 和节点 2 之间没有边，因为 |nums[0] - nums[2]| = |2 - 6| = 4，大于 maxDiff。
查询 [1,3]：节点 1 和节点 3 之间存在路径通过节点 2，因为 |nums[1] - nums[2]| = |5 - 6| = 1 和 |nums[2] - nums[3]| = |6 - 8| = 2，都小于等于 maxDiff。
查询 [2,3]：节点 2 和节点 3 之间有一条边，因为 |nums[2] - nums[3]| = |6 - 8| = 2，等于 maxDiff。
因此，在处理完所有查询后，最终答案为 [false, false, true, true]。

说明：

1 <= n == nums.length <= 10^5
0 <= nums[i] <= 10^5
nums 按非递减顺序排序。
0 <= maxDiff <= 10^5
1 <= queries.length <= 10^5
queries[i] == [ui, vi]
0 <= ui, vi < n

思路

有 n 个节点编号为 0 ~ n - 1，节点之间的边由非递减数组 nums 与变量 maxDiff 给出，如果两个节点的差值不超过 maxDiff 则表示它们之间有一条无向边。有一个查询数组 queries，返回每次查询的两个节点是否连通。

由于 nums 非递减，只需考虑相邻节点是否连通即可。如果相邻节点不连通，那么跨过这对节点的区间都不连通。可以使用并查集维护连通性。

代码


/**
 * @date 2026-07-09 8:50
 */
public class PathExistenceQueries3532 {

    class UnionFind {
        private final int[] fa;

        public UnionFind(int n) {
            fa = new int[n];
            Arrays.setAll(fa, i -> i);
        }

        public int find(int i) {
            if (i != fa[i]) {
                fa[i] = find(fa[i]);
            }
            return fa[i];
        }

        public void union(int a, int b) {
            int x = find(a);
            int y = find(b);
            if (x < y) {
                fa[y] = x;
            } else if (x > y) {
                fa[x] = y;
            }
        }
    }

    public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        UnionFind uf = new UnionFind(n);
        for (int i = 1; i < n; i++) {
            if (Math.abs(nums[i] - nums[i - 1]) <= maxDiff) {
                uf.union(i, i - 1);
            }
        }
        boolean[] res = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            res[i] = uf.find(queries[i][0]) == uf.find(queries[i][1]);
        }
        return res;
    }
}

性能

目标

给你一个长度为 m 的字符串 s，其中仅包含数字。另给你一个二维整数数组 queries，其中 queries[i] = [li, ri]。

对于每个 queries[i]，提取子串 s[li..ri]，然后执行以下操作：

将子串中所有非零数字按照原始顺序连接起来，形成一个新的整数 x。如果没有非零数字，则 x = 0。
令 sum 为 x 中所有数字的数字和。答案为 x * sum。

返回一个整数数组 answer，其中 answer[i] 是第 i 个查询的答案。

由于答案可能非常大，请返回其对 10^9 + 7 取余数的结果。

子串是字符串中的一个连续、非空字符序列。

示例 1：

输入： s = "10203004", queries = [[0,7],[1,3],[4,6]]
输出： [12340, 4, 9]
解释：
s[0..7] = "10203004"
    x = 1234
    sum = 1 + 2 + 3 + 4 = 10
    因此，答案是 1234 * 10 = 12340。
s[1..3] = "020"
    x = 2
    sum = 2
    因此，答案是 2 * 2 = 4。
s[4..6] = "300"
    x = 3
    sum = 3
    因此，答案是 3 * 3 = 9。

示例 2：

输入： s = "1000", queries = [[0,3],[1,1]]
输出： [1, 0]
解释：
s[0..3] = "1000"
    x = 1
    sum = 1
    因此，答案是 1 * 1 = 1。
s[1..1] = "0"
    x = 0
    sum = 0
    因此，答案是 0 * 0 = 0。

示例 3：

输入： s = "9876543210", queries = [[0,9]]
输出： [444444137]
解释：
s[0..9] = "9876543210"
    x = 987654321
    sum = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
    因此，答案是 987654321 * 45 = 44444444445。
    返回结果为 44444444445 mod (10^9 + 7) = 444444137。

说明：

1 <= m == s.length <= 10^5
s 仅由数字组成。
1 <= queries.length <= 10^5
queries[i] = [li, ri]
0 <= li <= ri < m

思路

有一个数字字符串 s，针对每一个子串 s[queries[i][0], queries[i][1]]，返回其非零数字所表示的数字乘以每位数字之和对 1000000007 取余的结果。

与 3754.连接非零数字并乘以其数字和I 相比，本题的数字是由 queries 给出的子串，需要返回每一个子串的结果。

数位和可以使用前缀和快速计算。子串非零数字所表示的数字也可以通过前缀计算。

区间 [l, r] 所表示的数字对 MOD 取模的值为 (prefixNum[r + 1] + MOD - prefixNum[l] * base[k] % MOD) % MOD，例如，1230456，[2, 4] 中的非零数字所表示的数字是 34，它等于 prefixNum[5]:1234 - prefixNum[2]:12 * 100，其中 100 = 10^k，k 表示 [l, r] 中非零数字的个数。

代码


/**
 * @date 2026-07-08 9:50
 */
public class SumAndMultiply3756 {

    public int[] sumAndMultiply(String s, int[][] queries) {
        int n = s.length();
        int[] prefix = new int[n + 1];
        int[] prefixLength = new int[n + 1];
        long[] prefixNum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            int d = s.charAt(i) - '0';
            prefix[i + 1] = prefix[i] + d;
            prefixLength[i + 1] = prefixLength[i] + (d != 0 ? 1 : 0);
            prefixNum[i + 1] = (prefixNum[i] * (d != 0 ? 10 : 1) + d) % MOD;
        }
        int ql = queries.length;
        int[] res = new int[ql];
        for (int i = 0; i < ql; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int sum = prefix[r + 1] - prefix[l];
            long x = (prefixNum[r + 1] + MOD - prefixNum[l] * base[prefixLength[r + 1] - prefixLength[l]] % MOD) % MOD;
            res[i] = (int) (x * sum % MOD);
        }
        return res;
    }

}

性能

3754.连接非零数字并乘以其数字和I

目标

给你一个整数 n。

将 n 中所有的非零数字按照它们的原始顺序连接起来，形成一个新的整数 x。如果不存在非零数字，则 x = 0。

sum 为 x 中所有数字的数字和。

返回一个整数，表示 x * sum 的值。

示例 1：

输入： n = 10203004
输出： 12340
解释：
非零数字是 1、2、3 和 4。因此，x = 1234。
数字和为 sum = 1 + 2 + 3 + 4 = 10。
因此，答案是 x * sum = 1234 * 10 = 12340。

示例 2：

输入： n = 1000
输出： 1
解释：
非零数字是 1，因此 x = 1 且 sum = 1。
因此，答案是 x * sum = 1 * 1 = 1。

说明：

0 <= n <= 10^9

思路

计算整数 n 的所有非零数字之和记为 sum，去掉 n 中的 0 形成的新整数记为 x，返回 x * sum 的值。

依题意模拟即可。

代码


/**
 * @date 2026-07-07 9:13
 */
public class SumAndMultiply3754 {

    public long sumAndMultiply(int n) {
        long sum = 0;
        long x = 0;
        int base = 1;
        while (n > 0) {
            int rem = n % 10;
            sum += rem;
            x += rem * base;
            base *= rem == 0 ? 1 : 10;
            n /= 10;
        }
        return x * sum;
    }
}

性能

1288.删除被覆盖区间

目标

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

说明：

1 <= intervals.length <= 1000
0 <= intervals[i][0] < intervals[i][1] <= 10^5
对于所有的 i != j：intervals[i] != intervals[j]

思路

有一个区间列表，删除被其它区间覆盖的区间，返回剩余的区间。区间 [a, b] 被区间[c, d] 覆盖需满足 c <= a && b <= d。

根据左端点从小到大排序，右端点从大到小排序。按顺序遍历排序后的数组，当前区间的左端点一定大于等于之前的区间的左端点，只需要判断右端点是否超过前面记录的最长右端点即可。

代码


/**
 * @date 2026-07-06 9:00
 */
public class RemoveCoveredIntervals1288 {

    public int removeCoveredIntervals(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, (a, b) -> {
            int compare = a[0] - b[0];
            return compare != 0 ? compare : b[1] - a[1];
        });
        int r = intervals[0][1];
        int res = 0;
        for (int i = 1; i < n; i++) {
            if (intervals[i][1] <= r) {
                res++;
            } else {
                r = intervals[i][1];
            }
        }
        return n - res;
    }
}

性能

2492.两个城市间路径的最小分数

目标

给你一个正整数 n ，表示总共有 n 个城市，城市从 1 到 n 编号。给你一个二维数组 roads ，其中 roads[i] = [ai, bi, distancei] 表示城市 ai 和 bi 之间有一条双向道路，道路距离为 distancei 。城市构成的图不一定是连通的。

两个城市之间一条路径的分数定义为这条路径中道路的最小距离。

返回城市 1 和城市 n 之间的所有路径的最小分数。

注意：

一条路径指的是两个城市之间的道路序列。
一条路径可以多次包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 。
测试数据保证城市 1 和城市n 之间至少有一条路径。

示例 1：

输入：n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
输出：5
解释：城市 1 到城市 4 的路径中，分数最小的一条为：1 -> 2 -> 4 。这条路径的分数是 min(9,5) = 5 。
不存在分数更小的路径。

示例 2：

输入：n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
输出：2
解释：城市 1 到城市 4 分数最小的路径是：1 -> 2 -> 1 -> 3 -> 4 。这条路径的分数是 min(2,2,4,7) = 2 。

说明：

2 <= n <= 10^5
1 <= roads.length <= 10^5
roads[i].length == 3
1 <= ai, bi <= n
ai != bi
1 <= distancei <= 10^4
不会有重复的边。
城市 1 和城市 n 之间至少有一条路径。

思路

单源最短路径，可以使用 Dijkstra 算法。但是需要注意，这里求的不是路径和的最小值，而是从城市 1 出发，每段路径的最小值。

从城市 1 开始 dfs 访问所能到达的城市，记录路径中的最小值。需要注意，虽然城市可能已访问过，但是边仍可能是未处理的，比如 1 -> 2 -> 3 -> 1，3 -> 1 这条路径也应该参与最终结果的计算，因此需要先比较再判断是否访问过。

代码


/**
 * @date 2026-07-06 11:35
 */
public class MinScore2492 {

    public int minScore(int n, int[][] roads) {
        List<int[]>[] g = new List[n + 1];
        Arrays.setAll(g, x -> new ArrayList<>());
        for (int[] road : roads) {
            g[road[0]].add(new int[]{road[1], road[2]});
            g[road[1]].add(new int[]{road[0], road[2]});
        }
        boolean[] visited = new boolean[n + 1];
        return dfs(1, g, visited);
    }

    public int dfs(int cur, List<int[]>[] g, boolean[] visited) {
        int res = Integer.MAX_VALUE;
        visited[cur] = true;
        for (int[] next : g[cur]) {
            res = Math.min(res, next[1]);
            if (visited[next[0]]) {
                continue;
            }
            res = Math.min(dfs(next[0], g, visited), res);
        }
        return res;
    }

}

性能

3286.穿越网格图的安全路径

目标

给你一个 m x n 的二进制矩形 grid 和一个整数 health 表示你的健康值。

你开始于矩形的左上角 (0, 0) ，你的目标是矩形的右下角 (m - 1, n - 1) 。

你可以在矩形中往上下左右相邻格子移动，但前提是你的健康值始终是正数。

对于格子 (i, j) ，如果 grid[i][j] = 1 ，那么这个格子视为不安全的，会使你的健康值减少 1 。

如果你可以到达最终的格子，请你返回 true ，否则返回 false 。

注意，当你在最终格子的时候，你的健康值也必须为正数。

示例 1：

输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
输出：true
解释：
沿着图中灰色格子走，可以安全到达最终的格子。

示例 2：

输入：grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3
输出：false
解释：
健康值最少为 4 才能安全到达最后的格子。

示例 3：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5
输出：true
解释：
沿着下图中灰色格子走，可以安全到达最终的格子。
任何不经过格子 (1, 1) 的路径都是不安全的，因为你的健康值到达最终格子时，都会小于等于 0 。

说明：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
2 <= m * n
1 <= health <= m + n
grid[i][j] 要么是 0 ，要么是 1 。

思路

有一个 m x n 的二进制矩阵，从左上角 (0, 0) 出发，可以沿上下左右四个方向移动到相邻的格子。如果经过的格子值为 1 视为不安全，健康度 health 减 1。判断是否存在路径使得到达 (m - 1, n - 1) 时，health > 0。

判断路径和是否严格小于 health，可以使用 Dijkstra 求出最短路。

代码


/**
 * @date 2026-07-02 9:09
 */
public class FindSafeWalk3286 {

    private final int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        int m = grid.size();
        int n = grid.get(0).size();
        int[][] dis = new int[m][n];
        for (int[] row : dis) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        // 出错点：不要忘了初始化
        dis[0][0] = grid.get(0).get(0);
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0});
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int r = p[0], c = p[1];
            for (int[] d : directions) {
                int nr = r + d[0];
                int nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && dis[r][c] + grid.get(nr).get(nc) < dis[nr][nc]) {
                    Integer cost = grid.get(nr).get(nc);
                    dis[nr][nc] = dis[r][c] + cost;
                    if (cost == 0) {
                        q.offerFirst(new int[]{nr, nc});
                    } else {
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
        }
        return dis[m - 1][n - 1] < health;
    }

}

性能

1358.包含所有三种字符的子字符串数目

目标

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都至少出现过一次的子字符串数目。

示例 1：

输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。

示例 2：

输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。

示例 3：

输入：s = "abc"
输出：1

说明：

3 <= s.length <= 5 x 10^4
s 只包含字符 a，b 和 c 。

思路

有一个字符串只包含三个字符 a b c，求这三个字符至少出现一次的子串个数。

直接的想法是计算这三个字符出现次数的前缀和，然后使用滑动窗口。使用前缀和来判断窗口内的子串是否满足条件，如果 [l, r] 满足条件，那么 [l, r ~ n - 1] 也满足条件。

判断字符是否至少出现一次可以不用前缀和，使用三个变量记录它们上次出现的下标，如果小于左端点则用 -1 标记。

代码


/**
 * @date 2026-06-30 9:14
 */
public class NumberOfSubstrings1358 {

    public int numberOfSubstrings(String s) {
        int n = s.length();
        int a = -1, b = -1, c = -1;
        int l = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'a') {
                a = i;
            } else if (s.charAt(i) == 'b') {
                b = i;
            } else {
                c = i;
            }
            while (a >= 0 && b >= 0 && c >= 0) {
                res += n - i;
                if (a <= l) {
                    a = -1;
                } else if (b <= l) {
                    b = -1;
                } else if (c <= l) {
                    c = -1;
                }
                l++;
            }
        }
        return res;
    }

}

2026 年 7 月
一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31