使用 indexOf 方法查找字符串中第一个唯一字符的教程

1. 理解 String 类的关键方法

在深入探讨查找唯一字符的逻辑之前，我们首先需要理解 Java String 类中两个核心方法的使用：charAt() 和 indexOf()。

1.1 charAt(int index) 方法

charAt(int index) 方法用于返回字符串中指定索引位置的字符。

• 语法: public char charAt(int index)
• 参数: index - 字符在字符串中的位置（从 0 开始）。
• 返回值: 指定索引处的字符。
• 示例: String s = "hello"; s.charAt(0) 将返回 'h'。

1.2 indexOf() 方法的重载形式

indexOf() 方法用于查找字符或子字符串在字符串中首次出现的位置。它有多种重载形式，其中两种对我们查找唯一字符至关重要：

• indexOf(char ch):

  • 语法: public int indexOf(char ch)
  • 参数: ch - 要查找的字符。
  • 返回值: 字符首次出现的索引。如果未找到，则返回 -1。
  • 示例: String s = "banana"; s.indexOf('a') 将返回 1。

• indexOf(char ch, int fromIndex):

  • 语法: public int indexOf(char ch, int fromIndex)
  • 参数:
    • ch - 要查找的字符。
    • fromIndex - 开始搜索的索引位置。
  • 返回值: 字符从 fromIndex 位置开始首次出现的索引。如果从 fromIndex 开始未找到，则返回 -1。
  • 示例: String s = "banana"; s.indexOf('a', 2) 将返回 3 (因为从索引 2 开始，'a' 首次出现在索引 3)。

2. 核心逻辑解析：如何判断字符唯一性

现在，我们来解析如何利用上述方法组合判断一个字符是否在字符串中是唯一的。核心判断条件是： s.indexOf(s.charAt(i), s.indexOf(s.charAt(i)) + 1) == -1

为了更好地理解这个表达式，我们将其分解：

1. s.charAt(i): 在循环的当前迭代中，这会获取字符串 s 在索引 i 处的字符。我们称之为 currentChar。
2. s.indexOf(currentChar): 这会查找 currentChar 在整个字符串 s 中首次出现的位置。例如，如果 s = "leetcode" 且 currentChar = 'l'，s.indexOf('l') 将返回 0。
3. s.indexOf(currentChar) + 1: 这将得到 currentChar 首次出现位置的下一个索引。这个值将作为我们第二次搜索的起始点。
4. s.indexOf(currentChar, s.indexOf(currentChar) + 1): 这是最关键的一步。它会从 currentChar 首次出现位置的下一个索引开始，再次查找 currentChar。
   • 如果 currentChar 是唯一的（即它只出现一次），那么从其首次出现位置的下一个索引开始，将无法再找到 currentChar。在这种情况下，indexOf() 方法会返回 -1。
   • 如果 currentChar 不是唯一的（即它出现了多次），那么从其首次出现位置的下一个索引开始，indexOf() 方法将能够找到 currentChar 的另一次出现，并返回其索引（一个非 -1 的值）。
5. == -1: 因此，当整个表达式 s.indexOf(s.charAt(i), s.indexOf(s.charAt(i)) + 1) == -1 为真时，就意味着 s.charAt(i) 在字符串中只出现了一次，它是一个唯一的字符。

3. 实现代码示例

下面是根据上述逻辑实现的 Java 代码，用于查找字符串中第一个唯一的字符的索引：

public class UniqueCharacterFinder {

    /**
     * 查找字符串中第一个不重复字符的索引。
     * 如果所有字符都重复，则返回 -1。
     *
     * @param s 输入字符串
     * @return 第一个不重复字符的索引，如果不存在则返回 -1
     */
    public static int findFirstUniqueCharIndex(String s) {
        // 遍历字符串中的每一个字符
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i); // 获取当前字符

            // 查找当前字符在字符串中首次出现的位置
            int firstOccurrenceIndex = s.indexOf(currentChar);

            // 从首次出现位置的下一个索引开始，再次查找当前字符
            // 如果从这个位置开始找不到该字符（即返回 -1），则说明它是唯一的
            if (s.indexOf(currentChar, firstOccurrenceIndex + 1) == -1) {
                return i; // 返回当前唯一字符的索引
            }
        }
        return -1; // 如果循环结束都没有找到唯一字符，则返回 -1
    }

    public static void main(String[] args) {
        String testString1 = "leetcode";
        System.out.println("字符串 \"" + testString1 + "\" 中第一个唯一字符的索引是: " + findFirstUniqueCharIndex(testString1)); // 预期输出: 0 (l)

        String testString2 = "loveleetcode";
        System.out.println("字符串 \"" + testString2 + "\" 中第一个唯一字符的索引是: " + findFirstUniqueCharIndex(testString2)); // 预期输出: 2 (v)

        String testString3 = "aabb";
        System.out.println("字符串 \"" + testString3 + "\" 中第一个唯一字符的索引是: " + findFirstUniqueCharIndex(testString3)); // 预期输出: -1
    }
}

4. 工作原理演示 (以 "leetcode" 为例)

让我们逐步跟踪 findFirstUniqueCharIndex("leetcode") 的执行过程：

Perl学习手札 chm版

Perl学习手札是台湾perl高手写的一篇文章，特打包为chm版，方便大家阅读。 关于本书 1. 关于Perl 1.1 Perl的历史 1.2 Perl的概念 1.3 特色 1.4 使用Perl的环境 1.5 开始使用 Perl 1.6 你的第一个Perl程序 2. 标量变量(Scalar) 2.1 关于标量 2.1.1 数值 2.1.2 字符串 2.1.3 数字与字符串转换 2.2 使用你自己的变量 2.3 赋值 2.3.1 直接设定 2.3.2 还可以这样 2.4 运算 2.5 变量的输出/输入 2.

下载

1. i = 0, currentChar = 'l':
   • s.indexOf('l') 返回 0。
   • s.indexOf('l', 0 + 1) 即 s.indexOf('l', 1)。从索引 1 开始，字符串 "eetcode" 中没有 'l'。所以 s.indexOf('l', 1) 返回 -1。
   • 条件 (-1 == -1) 为真，函数返回 i，即 0。

因此，对于 "leetcode"，函数会立即返回 0，因为 'l' 是第一个唯一的字符。

让我们再看一个例子："loveleetcode"

1. i = 0, currentChar = 'l':

   • s.indexOf('l') 返回 0。
   • s.indexOf('l', 0 + 1) 即 s.indexOf('l', 1)。从索引 1 开始，字符串 "oveleetcode" 中存在 'l'（在索引 8）。所以 s.indexOf('l', 1) 返回 8。
   • 条件 (8 == -1) 为假。继续循环。

2. i = 1, currentChar = 'o':

   • s.indexOf('o') 返回 1。
   • s.indexOf('o', 1 + 1) 即 s.indexOf('o', 2)。从索引 2 开始，字符串 "veleetcode" 中存在 'o'（在索引 9）。所以 s.indexOf('o', 2) 返回 9。
   • 条件 (9 == -1) 为假。继续循环。

3. i = 2, currentChar = 'v':

   • s.indexOf('v') 返回 2。
   • s.indexOf('v', 2 + 1) 即 s.indexOf('v', 3)。从索引 3 开始，字符串 "eleetcode" 中没有 'v'。所以 s.indexOf('v', 3) 返回 -1。
   • 条件 (-1 == -1) 为真，函数返回 i，即 2。

因此，对于 "loveleetcode"，函数返回 2，因为 'v' 是第一个唯一的字符。

5. 注意事项与性能考量

• 时间复杂度: 尽管 indexOf 方法在 Java 内部经过高度优化，但在最坏情况下，每次 indexOf 调用都可能需要遍历字符串的一部分。在一个循环中嵌套 indexOf 调用，使得这种方法的整体时间复杂度接近 O(N^2)，其中 N 是字符串的长度。对于非常长的字符串，这可能导致性能问题。
• 空间复杂度: 这种方法不使用额外的数据结构，因此空间复杂度为 O(1)。
• 替代方案: 对于性能要求较高的场景，更优化的方法是使用哈希表（HashMap 或 int[26] 数组用于小写英文字母）来记录每个字符的出现频率。这种方法通常具有 O(N) 的时间复杂度，因为它只需要对字符串进行一到两次遍历。

6. 总结

通过巧妙地组合使用 String 类的 charAt() 和 indexOf() 方法，我们可以实现查找字符串中第一个唯一字符的功能。核心在于利用 indexOf(char ch, int fromIndex) 方法从字符首次出现位置的下一个索引开始进行二次查找。如果二次查找返回 -1，则表明该字符是唯一的。尽管这种方法在简洁性上表现出色，但在处理极端长度的字符串时，应考虑其 O(N^2) 的时间复杂度，并根据实际需求权衡是否采用更高效的基于哈希表的解决方案。