給定整數陣列
nums，如果陣列中有任何值出現至少兩次則回傳true，若每個元素都不同則回傳false。
Example:
Input: nums = [1,2,3,1] Output: true
Intuition
TIP
核心思路：看到「是否有重複」就想到 HashSet——邊遍歷邊加入，遇到已存在的元素就代表有重複。
- 最直觀的方式是排序後檢查相鄰元素是否相同
- 更高效的做法是利用 HashSet 的 O(1) 查找特性
Approaches
1. Sorting — O(n log n) / O(1)
- Idea: 排序後，重複元素必定相鄰，只需線性掃描檢查相鄰元素
- Time:
O(n log n)- 排序主導 - Space:
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 — O(n) / O(n)
- Idea: 邊遍歷邊把元素加入 HashSet，若加入時已存在則代表有重複
- Time:
O(n)- 單次遍歷，HashSet 操作平均 O(1) - Space:
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
- Key trick: Kotlin
HashSet.add回傳Boolean，可一行同時完成「加入 + 判斷是否已存在」