[LeetCode] 1. Two Sum

Problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

我沒有預設答案只有一組,也沒有預設陣列中不能有相同的數字。起初一直想寫出效能好的解法,但苦毫無進展,索性直接先寫出最無腦的暴力解法。

最先想到的是暴力解法。

以前述的例子為例,

圖一

依次取出陣列中的數字,如圖一,取出第一個數字為 2,與其後的三個數字相加。其實第一組相加 2+7 總和已符合目標數字 9,回傳答案為 [0, 1]。

圖二

取出第二個數字為 7,如圖二,在與其後二個數字相加。第二個數字 7 之所以不需要與前面的數字 2 相加是因為已經加過了(圖一的 2+7)。

圖三

接著繼續取出第三個數字 11,如圖三,與其後第四個數字相加。

圖四

如圖四,直到取出最後一個數字為止。

執行效能如下:

| 執行時間 | 時間複雜度 | 空間複雜度 |
|:-------:|:--------:|:--------:|
| 44 ms | O(n​²) | O(n​²) |

第二個解法是偷參考解答,才採用雜湊表(Hash Table),因為雜湊表的時間複雜度為 O(1)。

由暴力解法延伸並偷參考解答。

而由暴力解法延伸,不需一開始就先把所有數字加入雜湊表中,而是將依次取出的數字與雜湊表中檢視過的數字相加,若總和不符合目標數字就加到雜湊表中,以待陣列中的其他數字與它相加符合目標數字。

圖五

取出第一個數字 2,如圖五,但雜湊表中沒有數字可以配對,以數字為 Key,index 值為 Value,將 {2, 0} 加入雜湊表。

圖六

依次取出第二個數字 7,如圖六,找出符合 9–7 的 Key 值。(其實第一組 2 已符合 9–7,回傳答案為 [0, 1]。)若查無符合則將 {7, 1} 加入雜湊表。

圖七

依次取出第三個數字 11,如圖七,找出符合 9–11 的 Key 值。若查無符合則將 {11, 2} 加入雜湊表,以待陣列中的其他數字與它相加符合目標數字。

圖八

最後取出第四個數字 15,如圖八,找出符合 9–15 的 Key 值。若查無符合則回傳 {-1, -1}。

值得注意的是第 8 行和第 10 行被註解掉的程式碼是多餘的判斷,原因是當加入(put)HashMap 的 Key 值重複時,則會更新同 Key 值所對應的 Value 值。未移除重複的 Key 值判斷時,執行時間為 10 ms,移除判斷後,其執行效能如下:

| 執行時間 | 時間複雜度 | 空間複雜度 |
|:-------:|:--------:|:--------:|
| 7 ms | O(n​) | O(n​) |

在此要特別探討,如果輸入的陣列無解,應該要回傳什麼?

可以確定的是回傳 new int[2],即是以回傳 [0, 0] 代表無解,絕對是不適當的,因為第 0 項與第 0 項相加就是一種答案的組合。而以前述的程式碼是回傳 [-1, -1],因為在陣列中找不到符合的 element,照慣例是回傳 -1。更好的作法是拋出例外(Exception):

throw new IllegalArgumentException("No two sum solution");

,如此絕對不用擔心忘記處理收到index為 -1 的情境,而是針對例外做處理。