今天是Two Sum 跟 Best Time to Buy and Sell Stock

題目介紹

Two Sum
給定一個整數陣列 nums 和一個目標數字 target，找出陣列中兩個數字的索引，使得它們的和等於 target。

範例：
輸入: nums = [2,7,11,15], target = 9
輸出: [0,1]
解釋: nums[0] + nums[1] = 2 + 7 = 9

條件：

• 每個輸入只會有一個正確答案。
• 不能重複使用同一個元素。

解題思路

方法一：暴力解法（Brute Force）

• 兩層迴圈，檢查所有可能的組合。
• 時間複雜度 O(n²)，效率不佳。

方法二：使用 HashMap

• 建立一個 HashMap 紀錄「數字 → 索引」。
• 遍歷陣列時，檢查 target - nums[i] 是否存在於 HashMap 中。
• 若存在，代表找到解答；若不存在，將當前數字放進 HashMap。
• 時間複雜度 O(n)，空間複雜度 O(n)。

程式碼實作

Java 解法

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
return new int[] {};
}
}

Python 解法

class Solution:
def twoSum(nums, target):
hash_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_map:
return [hash_map[complement], i]
hash_map[num] = i

1. 初始化：hash_map = {}
2. 第一次迴圈，i = 0, num = 2，complement = 9 - 2 = 7，hash_map 裡沒有 7，將 2和 0 存入 hash_map → hash_map = {2: 0}。
3. 第二次迴圈，i = 1, num = 7，complement = 9 - 7 = 2，hash_map 裡有 2，說明找到了，回傳 [0, 1]。

複雜度分析

• 時間複雜度：O(n)，因為只需一次遍歷。
• 空間複雜度：O(n)，需要 HashMap / dict 存數字與索引。

兩個程式邏輯一樣，都是用HashMap在一次迴圈內找到答案，而Python 的語法更簡潔，字典 in 也比 map.containsKey 更好理解。

心得

這題作為 LeetCode 的開場題目，給一段時間沒寫程式的我重新熟悉程式語法。
學校是教Java但跟Java比起來Python方便很多，比較之後感受到不同語言的特性。

題目介紹

122. Best Time to Buy and Sell Stock II
     給定一個陣列 prices[i] 表示某支股票第 i 天的價格，設計演算法計算最大利潤。
     可以無限制買賣股票（但必須先賣出才能再買）。

程式碼實作

Java 解法（Greedy）

public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}

Python 解法（Greedy）

def maxProfit(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit

放個測試案例來看看對不對：

Case 1

python

print(maxProfit([7,1,5,3,6,4]))

• Day1=7 → Day2=1（跌價，不買）
• Day2=1 → Day3=5（漲價，賺4）
• Day3=5 → Day4=3（跌價，不買）
• Day4=3 → Day5=6（漲價，賺3）
• Day5=6 → Day6=4（跌價，不買）

總利潤 = 4 + 3 = 7

Case 2

python

print(maxProfit([1,2,3,4,5]))

• Day1=1 → Day2=2（賺 1）
• Day2=2 → Day3=3（賺 1）
• Day3=3 → Day4=4（賺 1）
• Day4=4 → Day5=5（賺 1）

總利潤 = 1+1+1+1 = 4
（等同於「Day1 買 Day5 賣」一次賺 4，結果一樣。）

Case 3

python

print(maxProfit([7,6,4,3,1]))

• 每天價格都在跌，永遠沒有「今天比昨天高」的情況。
• if 條件沒被觸發，profit 一直維持 0。

總利潤 = 0

雖然程式邏輯完全相同，但 Java 的語法需要嚴謹的結構，像是變數宣告必須加上型別 int profit = 0; ，陣列長度用 prices.length，for 迴圈也要寫成 for (int i = 1; i < prices.length; i++)。Python 就很簡潔，變數直接寫 profit = 0，陣列長度是 len(prices)，迴圈只要 for i in range(1, len(prices)):。

複雜度分析

＊時間複雜度：
整個演算法只用一個 for 迴圈，從第 1 天遍歷到最後一天，每次迭代只做一次比較與加法運算，沒有巢狀迴圈。
時間複雜度 = O(n)，其中 n 為天數。

＊空間複雜度：
演算法只使用了一個變數 profit 來記錄利潤，無論輸入多大都不會額外使用額外空間。
空間複雜度 = O(1)。

心得

這題考了貪婪法：

• 只要發現今天比昨天高，就直接在昨天買、今天賣，把漲幅拿下來。
• 因為不限交易次數，不需要去找「最佳買賣點組合」，只要把所有的上升區間都吃下來，累積起來就是最大利潤。
  所以其實不貪整段漲幅，只要把每個小漲幅都撿起來，最終還是可以得到最佳解。