“我報名參加金石計劃1期挑戰——瓜分10萬獎池，這是我的第1篇文章，點選檢視活動詳情”

題目

給定一個字串 s ，找到 它的第一個不重複的字元，並返回它的索引。如果不存在，則返回 -1。

示例 1：

• 輸入： s = "leetcode"
• 輸出： 0

示例 2：

• 輸入： s = "loveleetcode"
• 輸出： 2

示例 3：

• 輸入： s = "aabb"
• 輸出： -1

方法一：使用雜湊表儲存頻數

思路及解法

我們可以對字串進行兩次遍歷。

在第一次遍歷時，我們使用雜湊對映統計出字串中每個字元出現的次數。在第二次遍歷時，我們只要遍歷到了一個只出現一次的字元，那麼就返回它的索引，否則在遍歷結束後返回 −1。

程式碼

``` class Solution { func firstUniqChar(_ s: String) -> Int { var frequency: [Character : Int] = [:] for ch: Character in s { if nil != frequency[ch] { frequency[ch] = frequency[ch]! + 1 } else { frequency[ch] = 1 } }

    var index: Int = 0
    for ch: Character in s {
        if nil != frequency[ch] && frequency[ch]! == 1{
            return index
        }
        index += 1
    }
    return -1
}

} ```

複雜度分析

• 時間複雜度：$O(n)$，其中 $n$ 是字串 $s$ 的長度。我們需要進行兩次遍歷。

• 空間複雜度：$O(|\Sigma|)$，其中 $\Sigma$ 是字符集，在本題中 $s$ 只包含小寫字母，因此 $|\Sigma| \leq 26$。我們需要 $O(|\Sigma|)$ 的空間儲存雜湊對映。

方法二：使用雜湊表儲存索引

思路及解法

我們可以對方法一進行修改，使得第二次遍歷的物件從字串變為雜湊對映。

具體地，對於雜湊對映中的每一個鍵值對，鍵表示一個字元，值表示它的首次出現的索引（如果該字元只出現一次）或者 −1（如果該字元出現多次）。當我們第一次遍歷字串時，設當前遍歷到的字元為 $c$，如果 $c$ 不在雜湊對映中，我們就將 $c$ 與它的索引作為一個鍵值對加入雜湊對映中，否則我們將 $c$ 在雜湊對映中對應的值修改為 −1。

在第一次遍歷結束後，我們只需要再遍歷一次雜湊對映中的所有值，找出其中不為 −1 的最小值，即為第一個不重複字元的索引。如果雜湊對映中的所有值均為 −1，我們就返回 −1。

程式碼

``` class Solution { func firstUniqChar(_ s: String) -> Int { var position: [Character : Int] = [:] var i: Int = 0 for ch: Character in s { if nil != position[ch] { position[ch] = -1 } else { position[ch] = i } i += 1 }

    var first: Int = s.count
    for (_, pos) in position {
        if pos != -1 && pos < first {
            first = pos
        }
    }
    if first == s.count {
        first = -1
    }
    return first
}

} ```

複雜度分析

• 時間複雜度：$O(n)$，其中 $n$ 是字串 $s$ 的長度。第一次遍歷字串的時間複雜度為 $O(n)$，第二次遍歷雜湊對映的時間複雜度為 $O(|\Sigma|)$，由於 $s$ 包含的字元種類數一定小於 $s$ 的長度，因此 $O(|\Sigma|)$ 在漸進意義下小於 $O(n)$，可以忽略。

• 空間複雜度：$O(∣Σ∣)$，其中 $\Sigma$ 是字符集，在本題中 $s$ 只包含小寫字母，因此 $|\Sigma| \leq 26$。我們需要 $O(|\Sigma|)$ 的空間儲存雜湊對映。