Description
給定兩個整數陣列
nums1和nums2，回傳大小為 2 的列表answer：answer[0]是nums1中不在nums2的所有不重複元素，answer[1]是nums2中不在nums1的所有不重複元素。
Example:
Input: nums1 = [1,2,3], nums2 = [2,4,6] Output: [[1,3],[4,6]]
Intuition#
核心思路：將兩個陣列各轉成 Set，然後做集合差集運算。
- Set 天然去重，且支援 O(1) 查找
set1 - set2得到只在 nums1 中的元素set2 - set1得到只在 nums2 中的元素
Approaches#
1: Brute Force#
- 概念: 對 nums1 中每個元素檢查是否在 nums2 中，反之亦然
- 時間複雜度:
O(n * m)- 雙層遍歷 - 空間複雜度:
O(n + m)- 結果列表
class Solution {
fun findDifference(nums1: IntArray, nums2: IntArray): List<List<Int>> {
val diff1 = mutableSetOf<Int>()
val diff2 = mutableSetOf<Int>()
for (n in nums1) {
if (n !in nums2) diff1.add(n)
}
for (n in nums2) {
if (n !in nums1) diff2.add(n)
}
return listOf(diff1.toList(), diff2.toList())
}
}⭐2: HashSet Difference#
- 概念: 轉成 Set 後直接用集合差集
- 時間複雜度:
O(n + m)- 建 Set + 差集運算 - 空間複雜度:
O(n + m)- 兩個 Set
class Solution {
fun findDifference(nums1: IntArray, nums2: IntArray): List<List<Int>> {
val set1 = nums1.toHashSet()
val set2 = nums2.toHashSet()
return listOf(
(set1 - set2).toList(),
(set2 - set1).toList()
)
}
}Kotlin 的
Set支援-運算子做差集，語法簡潔。底層是 O(n) 遍歷較小集合，對每個元素做 O(1) 查找。
🔑 Takeaways#
- Pattern: 集合差異 / 對稱差 -> HashSet 差集運算
- 關鍵技巧: Kotlin 的集合運算子（
-、intersect、union）讓程式碼非常簡潔。記得先轉 Set 去重