Two Sum 是刷 Leetcode 的人必刷的經典題目，通常也是第一題。儘管我已經解決過了，但我希望自己可以明確清楚的解釋自己的思路，所以我還是寫了一篇Leetcode 解題文章。那麼我們開始吧
Two Sum
題目描述
給定一個陣列nums與整數target，回傳陣列中兩個加總等於 target 的元素之 index。題目明確寫道，答案只有一個。
解題思路
Solution 1
第一直覺就是暴力解，做法是使用兩層 for 迴圈，一旦找到相等就要立刻return。Java實現如下：
public int[] twoSum(int[] nums, int target) {
// find two element that sum up equals to target
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
int ans = nums[i]+nums[j];
if(ans==target) return new int[]{i,j};
}
}
return new int[]{-1,-1};
}這樣能夠解決問題，時間複雜度是O(n²)，最壞情況下需比較約 n²/2 次，故為 O(n²)，相當耗時。空間複雜度是O(1)，因為並沒有使用更多的資料結構。
Solution 2
接著這題的正確解法是利用HashMap方式，才能將時間複雜度從 O(n²) 降至 O(n)。解決思路如下： 定義一個HashMap保存陣列中的值與index，並且在 target - nums[i] 作為 complement 的結果可以在 HashMap 中被找到的話，就代表找到配對了。Java實現如下
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(!map.containsKey(target-nums[i])){
map.put(nums[i],i);
} else {
return new int[]{map.get(target-nums[i]),i};
}
}
return new int[]{-1,-1};
}這個解法的時間複雜度為O(n)，因為n個元素只需要跑n次，空間複雜度：O(n)，最差情況下n筆資料要存n次。
總結
Two Sum 雖然是一道簡單題，但它其實涵蓋了幾個重要觀念：
- 暴力解與最佳解的差異
- HashMap 的查詢特性
- 空間換時間
- 時間複雜度分析
這也是為什麼它會成為 Leetcode 最經典的入門題之一。
Two Sum 的精髓在於：與其找兩個數，不如記住已見過的數，再找它的『另一半』。這個思維也適用於許多其他題目。
Remove Duplicates from Sorted Array
題目描述
定義一個從小到大的陣列，在原陣列上原地操作，使前 k 個元素為不重複的有序元素，並回傳 k。
解題思路
Solution 1
我會使用一個for迴圈掃描陣列，並且定義一個pointer值。pointer值初始是0。 陣列中掃描元素同時與上一個做比較，如果與上一個元素相同，代表重複，pointer值+1。 pointer的用途是將當前陣列值移動到當前位置-pointer的新位置。 最後移除後的陣列長度就是nums.length-pointer。
用Java實現的邏輯就是
public int removeDuplicates(int[] nums) {
int duplicates=0;
for(int i=1;i<nums.length;i++){
if (nums[i]==nums[i-1]) {
duplicates +=1;
}
nums[i-duplicates] = nums[i];
}
return nums.length-duplicates;
}Solution 2
除此之外，還可以使用更簡潔的解決方法，邏輯類似，只是slow pointer會在不重複的時候增加，重複時不變動。
public int removeDuplicates(int[] nums) {
int slow = 1;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}總結
兩者都一樣，時間複雜度O(n)、空間複雜度O(1)。
兩種解法的核心思維相同：用一個 pointer 追蹤「下一個有效寫入位置」， 差別在於 Solution 1 以「重複數量」作為偏移量，Solution 2 則是顯式的 fast/slow pointer， 面試時 Solution 2 語意更清楚，建議優先使用。
Best Time to Buy and Sell Stock
題目描述
題目給定一個陣列，元素代表股價，請在陣列中計算出可以獲得的最大利益。
解題思路
利益最大就代表要找出陣列的最小值，以及計算出最小值與元素相比相差最大的，就是最大利潤。 Java解法如下。
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for(int price: prices) {
// calculate min price
minPrice = Math.min(minPrice,price);
int profit = price-minPrice;
maxProfit = Math.max(maxProfit,profit);
}
return maxProfit;
}總結
時間複雜度為O(n)，空間複雜度為O(1)
Best Time to Buy and Sell Stock 的精髓在於： 不需要枚舉所有買賣組合，只要邊掃描邊維護「目前最低價」， 就能在 O(n) 內找到最大利潤。