Description
給定整數陣列
nums，如果陣列中有任何值出現至少兩次則回傳true，若每個元素都不同則回傳false。
Example:
Input: nums = [1,2,3,1] Output: true
Intuition#
核心思路：看到「是否有重複」就想到 HashSet——邊遍歷邊加入，遇到已存在的元素就代表有重複。
- 最直觀的方式是排序後檢查相鄰元素是否相同
- 更高效的做法是利用 HashSet 的 O(1) 查找特性
Approaches#
1: Sorting#
- 概念: 排序後，重複元素必定相鄰，只需線性掃描檢查相鄰元素
- 時間複雜度:
O(n log n)- 排序主導 - 空間複雜度:
O(1)- 原地排序（或 O(n) 取決於排序實作）
class Solution {
fun containsDuplicate(nums: IntArray): Boolean {
nums.sort()
for (i in 1 until nums.size) {
if (nums[i] == nums[i - 1]) return true
}
return false
}
}⭐2: HashSet#
- 概念: 遍歷陣列，嘗試將每個元素加入 Set，若
add回傳false表示該元素已存在，即有重複 - 時間複雜度:
O(n)- 遍歷一次，每次 Set 操作 O(1) - 空間複雜度:
O(n)- 最壞情況存入所有元素
class Solution {
fun containsDuplicate(nums: IntArray): Boolean {
val seen = HashSet<Int>()
for (num in nums) {
if (!seen.add(num)) return true
}
return false
}
}🔑 Takeaways#
- Pattern: 重複檢測 -> HashSet 是最直接的工具
- 關鍵技巧:
HashSet.add()回傳Boolean，可以同時完成「檢查」和「加入」兩個動作，非常簡潔