牛客劍指 Offer：查找字符串中第一個只出現一次的字符下標

題目描述

給定一個字符串，找到第一個只出現一次的字符的下標（從 0 開始）。若不存在，返回 -1。字符串長度範圍 1~10000。

解題思路：雙向掃描法

對於當前字符 str[i]，分別向後與向前掃描：

1. 向後掃描（j = i+1 到末尾），若發現相同字符，說明非唯一，跳出。
2. 向前掃描（k = i-1 到開頭），若發現相同字符，說明非唯一，跳出。
3. 若向後掃描到末尾（j == n）且向前掃描到開頭（k < 0），則 str[i] 為第一個唯一字符，返回 i。
4. 若遍歷完畢仍未找到，返回 -1。

C++ 代碼實現

#include <iostream>
#include <string>
using namespace std;

int FirstNotRepeatingChar(string str) {
    int n = str.length();
    if (n < 1 || n > 10000) return -1;

    for (int i = 0; i < n; ++i) {
        int j, k;
        // 向後查找
        for (j = i + 1; j < n; ++j) {
            if (str[i] == str[j]) break;
        }
        // 向前查找
        for (k = i - 1; k >= 0; --k) {
            if (str[i] == str[k]) break;
        }
        // 判斷是否唯一
        if (j == n && k < 0) {
            return i;
        }
    }
    return -1;
}

int main() {
    string s = "aabccdbd";
    cout << FirstNotRepeatingChar(s) << endl; // 輸出: 2 (字符 'b')
    return 0;
}

優化建議

上述雙層循環時間複雜度為 O(n²)。更優解法：

1. 第一遍遍歷統計各字符頻率（哈希表/數組），O(n)。
2. 第二遍遍歷找第一個頻率為 1 的字符，O(n)。
3. 總時間 O(n)，空間 O(1)（字符集固定）。

// 優化版
int FirstNotRepeatingCharOptimized(string str) {
    int count[256] = {0};
    for (char c : str) count[c]++;
    for (int i = 0; i < str.size(); ++i)
        if (count[str[i]] == 1) return i;
    return -1;
}