題目描述:給定一個字串 s,找到第一個不重複的字元並回傳它的索引。若不存在,回傳 -1。
解題思路:先遍歷一次字串,用大小為 26 的陣列(因為只有小寫字母)統計每個字元的出現次數。再遍歷一次字串,找到第一個計數為 1 的字元,回傳其索引。兩次遍歷各 O(n),總時間 O(n)。
時間複雜度:O(n) — 兩次遍歷字串,n 為字串長度。
空間複雜度:O(1) — 固定大小 26 的計數陣列(字元集大小固定)。
1. Create count array of size 26, initialized to 0 2. First pass: for each character c in s, increment count[c - 'a'] 3. Second pass: for each index i in s: a. If count[s[i] - 'a'] == 1, return i 4. Return -1
雜湊表記錄首次出現位置 O(n):用 unordered_map 記錄每個字元第一次出現的索引和出現次數。最後遍歷雜湊表找計數為 1 且索引最小的。時間相同但雜湊表的常數因子較大。
佇列 + 計數 O(n):用佇列按出現順序記錄字元。遍歷時入隊並計數,最後從隊首開始彈出直到找到計數為 1 的字元。適合串流場景但對此題而言過於複雜。