博文中会简要介绍Leetcode P0260题目分析及解题思路。
“Single Number III”是一道中等难度的题目，依据题目要求，我们可以利用集合（或哈希表）来去重得到非重复的两个数。
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
Follow up: Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
以下是Java的题解代码实现。
class Solution {
public int[] singleNumber(int[] nums) {
Set<Integer> unmatched = new HashSet<>();
for (int n: nums) {
if (unmatched.contains(n)) {
unmatched.remove(n);
}
else {
unmatched.add(n);
}
}
int[] ret = new int[2];
int idx = 0;
for (int n: unmatched) {
ret[idx] = n;
++idx;
}
return ret;
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
unordered_set<int> unmatched;
for (int n: nums) {
if (unmatched.count(n)) {
unmatched.erase(n);
}
else {
unmatched.insert(n);
}
}
vector<int> ret;
for (int n: unmatched) {
ret.push_back(n);
}
return ret;
}
};