📘 題目敘述
給定兩個整數陣列 nums1 與 nums2，請回傳一個長度為 2 的答案陣列 ans：
ans[0]：所有只出現在nums1、但不出現在nums2的不同整數ans[1]：所有只出現在nums2、但不出現在nums1的不同整數
回傳的每個列表中元素順序不限，但必須是「不同的整數」（去重後）。
條件限制
1 <= nums1.length, nums2.length <= 1000-1000 <= nums1[i], nums2[i] <= 1000
🧠 解題思路
我的做法是：
- 先把
nums1、nums2都排序 - 用兩個指標
p1、p2同步掃過兩個排序後的陣列（類似 merge 的感覺） - 當某邊的數比較小，表示那個數「目前在另一邊還沒出現」，可以先加入對應答案
- 若兩邊相等，表示兩邊都有這個數 → 兩邊都跳過
- 因為排序後會有重複值連在一起，所以我用
b1、b2記錄「上一個已加入的值」，避免重複 push
最後如果其中一個陣列先掃完，另一邊剩下的值就全部都是「只出現在自己這邊」的，繼續去重後加入即可。
所有變數
（照你要求：所有變數是 ###，裡面用 -）
所有變數
ans：答案，ans[0]放只在nums1的值，ans[1]放只在nums2的值b1：記錄「最近一次加入ans[0]的值」，用來去重（避免同值重複加入）b2：記錄「最近一次加入ans[1]的值」，用來去重p1：掃描nums1的指標p2：掃描nums2的指標n1：nums1長度n2：nums2長度
🪜 主要流程步驟
第一步：排序
- 先
sort(nums1)、sort(nums2) - 這樣相同的值會黏在一起，方便去重
- 也能用 two pointers 直接比較大小前進
第二步：雙指標同步掃描（主 while）
在 p1 < n1 && p2 < n2 時，分三種情況：
情況一：nums1[p1] < nums2[p2]
- 代表
nums1[p1]這個值「比 nums2 目前看到的值還小」 - 因此它不可能在
nums2出現於p2之前（因為 nums2 已排序） - 所以可以判定：這個值是「只出現在 nums1」的候選
- 為了避免重複（例如 nums1 有很多相同值），我用
b1去重：
- 若
b1 != nums1[p1]才加入ans[0]
然後 p1++ 前進
情況二：nums2[p2] < nums1[p1]
- 完全對稱：這個值只會是「只出現在 nums2」的候選
- 用
b2去重後加入ans[1] p2++前進
情況三：nums1[p1] == nums2[p2]
- 代表兩邊都出現這個值 → 不應該出現在答案任何一邊
- 所以兩邊都前進：
p1++、p2++ - 同時把
b1、b2更新成這個值，避免後續同值又被加入
第三步：處理剩下沒掃完的一邊（尾端 while）
如果主 while 結束後：
nums1 還有剩
- 代表
nums2已經掃完了 - 剩下的
nums1[p1...]全部都不可能在 nums2 裡面出現 - 直接用
b1去重後加入ans[0]
nums2 還有剩
- 同理，用
b2去重後加入ans[1]
為什麼 b1 / b2 可以用來去重？
- 因為排序後，相同數字一定是連續出現
- 只要記住「上一個加入的數」，就能避免同一個數被連續加入多次
💻 程式碼實作
class Solution {
public:
vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> ans(2);
int b1 = 10000, b2 = 10000;
int p1 = 0, p2 = 0;
int n1 = nums1.size();
int n2 = nums2.size();
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
while (p1 < n1 && p2 < n2) {
if (nums1[p1] < nums2[p2]) {
if (b1 != nums1[p1]) {
b1 = nums1[p1];
ans[0].push_back(b1);
}
p1++;
} else if (nums2[p2] < nums1[p1]) {
if (b2 != nums2[p2]) {
b2 = nums2[p2];
ans[1].push_back(b2);
}
p2++;
} else {
b1 = nums1[p1];
b2 = nums2[p2];
p1++;
p2++;
}
}
while (p1 < n1) {
if (b1 != nums1[p1]) {
b1 = nums1[p1];
ans[0].push_back(b1);
}
p1++;
}
while (p2 < n2) {
if (b2 != nums2[p2]) {
b2 = nums2[p2];
ans[1].push_back(b2);
}
p2++;
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/find-the-difference-of-two-arrays/