LC.P2599[统计范围内的元音字符串数]

方法一：前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] vowelStrings(String[] words, int[][] queries) {
        // Set<Character> set = new HashSet<>(List.of('a', 'e', 'i', 'o', 'u'));
        Set<Character> set = Set.of('a', 'e', 'i', 'o', 'u');
        int n = words.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            String word = words[i - 1];
            int length = word.length();
            boolean flag = set.contains(word.charAt(0)) && set.contains(word.charAt(length - 1));
            sum[i] = sum[i - 1] + (flag ? 1 : 0);
        }
        n = queries.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = sum[r + 1] - sum[l];
        }
        return ans;
    }
}
  • 时间复杂度：$O(n + m)$，$n$和$m$分别为$words$与$queries$的长度
  • 空间复杂度：$O(n)$