【學習筆記 - DSA】Two Sum, Contains Duplicate

Zhi Liu

發佈於程式碼

2025/12/29 更新2025/12/29 發佈閱讀 5 分鐘

Two Sum

Two Sum 是最經典的「用 Hash Table 將 O(n²) 優化成 O(n)」的入門題，非常適合用來理解 Hashing 的核心價值。

給定一個整數陣列 nums 與一個整數 target，請找出 兩個不同索引的數字，使得它們的和等於 target。

每個輸入只會有一組解
同一個元素不能使用兩次
回傳的是原始陣列中的索引

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

解法 1：Brute Force (Array)

最直覺的方式：依序嘗試所有可能的兩兩組合。

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return []; 
}

解法 2：Hash Table

利用 Hash Table「快速查找」的特性
一邊遍歷陣列，一邊記錄已看過的數字

核心想法是：

當前數字是 num
我需要的另一個數是 target - num
如果這個數之前出現過，就直接找到答案

function twoSum(nums: number[], target: number): number[] {
	const numIndexMap = new Map<number, number>();
	for (let i = 0; i < nums.length; i++) {
		const num = nums[i];
		const complement = target - num;
		if (numIndexMap.has(complement)) {
			return [numIndexMap.get(complement)!, i];
		}
		numIndexMap.set(num, i);
	}
	return [];
}

Contains Duplicate

這題可以直觀感受 Set「只保留唯一值」的特性，也是理解 Hash-based 結構最直覺的案例之一。

給定一個整數陣列 nums，請判斷陣列中是否存在任意一個數字重複出現至少兩次。

如果有重複，回傳 true
否則回傳 false

Input: nums = [1, 2, 3, 1]
Output: true

Input: nums = [1, 2, 3, 4]
Output: false

解法 1：Set

Set 只會保留「唯一值」
如果 Set 的大小比原陣列小，就代表有重複

function containsDuplicate(nums: number[]): boolean {
    const uniqueElements = new Set(nums);
    return uniqueElements.size < nums.length;
}

解法 2：Sort

如果陣列排序後，有任意兩個相鄰元素相同，就代表存在重複

注意：此解法會改變原陣列順序，因此實務上需確認是否允許修改輸入資料。

function containsDuplicate(nums: number[]): boolean {
    const sortedNums = nums.slice().sort((a, b) => a - b);

    for (let i = 0; i < sortedNums.length - 1; i++) {
        if (sortedNums[i] === sortedNums[i + 1]) {
            return true;
        }
    }

    return false;
}