這題是CTCI上的第一題，也是這系列第一題講到的CTCI題目。作為避免直接勸退的一題，本題的難度也不高，所以有不同的解法來讓大家自由發揮。

讓我們來看看題目的內容（已翻譯成中文）：

" 在不使用其他資料結構的情況下，寫一個演算法來判斷字串內的所有字元都是unique的（不重複的意思） "

那在開始前不乏提醒一下此系列的固定提醒：

這是一系列逐漸帶入解題的文章，難度會隨著進度增加，若還沒有讀過前面的文章，建議先從最前面開始來逐漸練習解題喔！

好，讓我們開始吧

如同前面文章所說「先求有再求好」，直覺想到暴力解並不是壞事。可能已經有讀者想到用迴圈包迴圈，來逐一去比較了。

static boolean isUnique(String s) {
	for(int i = 0 ; i < s.length() ; i++) {
		for(int j = 0 ; j < s.length() ; j++) {
			if(i == j) continue; // 不和自己比
			if(s.charAt(i)==s.charAt(j)) return false;
                        // 如果有相同，代表有重複字元
		}
	}
	return true; // 跑完迴圈代表都不重複
}

這個解法真的十分經典，甚至在學校考題中也會出現類似應用的題目呢

又或者是，先把字串中的字元先排好順序，兩個一組檢查是否有重複
從第二個字元開始兩個一組，檢查到最後一個字元，如果同一組中的字元相同，就代表字串中有重複（同邏輯下，也可以從第一個開始一組，比到倒數第二個）

static boolean isUnique(String s) {
	char[] arr = s.toCharArray(); // 先轉成字元陣列
	Arrays.sort(arr); // 排好順序
	for(int i = 1 ; i < arr.length ; i++) {
		if(arr[i]==arr[i-1]) return false; 
                // 兩兩相同就是有重複
	}
	return true;
}

舉個例子：
假設我們輸入"apple"，就會先把"apple"變成陣列的['a','p','p','l','e']，再依照字母順序排列好，就會變成成['a', 'e', 'l', 'p', 'p']

此時我們兩個一組開始比較，從第二個字元開始比到最後一個

1. e ≠ a
2. l ≠ e
3. p ≠ l
4. p = p → 有重複！

以上都是可行的解法，但單純這樣似乎有點太單調了，所以接下來會講解另一種解法，也先為我們日後會講到的題目鋪梗。

不知道大家有沒有聽過ASCII這個東西呢？

沒錯！每個字元都可以變成一個數字，如果我們運用這個原理，開一個夠大的Boolean陣列，把字元轉換成對應的ASCII。再依照ASCII的數字，在陣列內紀錄誰已經出現過了，如果下次要再紀錄時發現這個字元紀錄過，就代表有重複！

不好理解嗎？那我們把它想像成開燈泡吧

1. 先建立一整排夠記錄所有字元的燈泡來做紀錄，這些燈泡一開始都是關著的
2. 我們訂一個規則，用ASCII給對應的字元一個數字，就想像成是第N個燈泡吧
3. 開始依序讀字串中的字元，假設先讀到A好了，我們依照ASCII的編號，去把代表A的燈泡打開
4. 接著往下讀字元，假設又碰到要打開A時，我們發現代表A的燈泡已經打開了，就代表字元有重複

（參考下圖）

這樣是不是比較好懂了呢？

另外能幫程式省一點時間的是，ASCII就128個字元，如果要在不重複的情況下組出最長的字串，最長一定是128，再多一定會有重複。
就好比可以拿鐵、人、賽三個字造句，不重複的話，最長也就三個字

所以最終可以得到這段程式碼

static boolean isUnique(String s) {
    if(s.length() > 128) return false; // 超過128就一定重複
    boolean[] chars = new boolean[128]; 
    // 建一個紀錄出現過的陣列
    for(int i = 0 ; i < s.length() ; i++) {
    	if(chars[s.charAt(i)]) return false;
    	else chars[s.charAt(i)] = true;
        // 如果對應的燈泡已經打開就代表重複
        // 沒有的話，就把燈泡打開
    }
    return true; // 跑完就代表沒出現重複
}

提醒：
如果題目不是使用ASCII，而是使用Unicode的話，陣列大小就不是128嘍！
請視情況做大小的調整

小結：
今天我們看了用陣列紀錄的方法，而這個方法類似的應用也不少，明天我們就來一題類似的題目，給大家小試身手一下吧