LeetCode 2032: Two Out of Three (Per-Array Dedup + Bitmask Presence)
LeetCode 2032Hash TableBitmaskToday we solve LeetCode 2032 - Two Out of Three.
Source: https://leetcode.com/problems/two-out-of-three/
English
Problem Summary
Given three integer arrays nums1, nums2, and nums3, return all distinct values that appear in at least two arrays. Order of output does not matter.
Key Insight
Duplicates inside the same array should count only once for that array. So we first deduplicate each array, then record in which arrays each value appears. A 3-bit mask is a compact way: bit 0 for nums1, bit 1 for nums2, bit 2 for nums3.
Algorithm
- Build three sets from the arrays to remove intra-array duplicates.
- For each value in set1, OR mask with 1; in set2 OR with 2; in set3 OR with 4.
- For every value-mask pair, if mask has at least two bits set, include the value in answer.
- A fast check is (mask & (mask - 1)) != 0, meaning at least two set bits.
Complexity Analysis
Let total length be n = len(nums1)+len(nums2)+len(nums3).
Time: O(n) average.
Space: O(n) for sets and map.
Common Pitfalls
- Counting duplicates from the same array multiple times (must deduplicate first).
- Confusing "at least two arrays" with "appears at least twice".
- Forgetting that answer order is unrestricted.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
Map<Integer, Integer> mask = new HashMap<>();
Set<Integer> s1 = new HashSet<>();
for (int x : nums1) s1.add(x);
for (int x : s1) mask.put(x, mask.getOrDefault(x, 0) | 1);
Set<Integer> s2 = new HashSet<>();
for (int x : nums2) s2.add(x);
for (int x : s2) mask.put(x, mask.getOrDefault(x, 0) | 2);
Set<Integer> s3 = new HashSet<>();
for (int x : nums3) s3.add(x);
for (int x : s3) mask.put(x, mask.getOrDefault(x, 0) | 4);
List<Integer> ans = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : mask.entrySet()) {
int m = e.getValue();
if ((m & (m - 1)) != 0) {
ans.add(e.getKey());
}
}
return ans;
}
}func twoOutOfThree(nums1 []int, nums2 []int, nums3 []int) []int {
mask := map[int]int{}
add := func(nums []int, bit int) {
seen := map[int]bool{}
for _, x := range nums {
if !seen[x] {
seen[x] = true
mask[x] |= bit
}
}
}
add(nums1, 1)
add(nums2, 2)
add(nums3, 4)
ans := make([]int, 0)
for x, m := range mask {
if m&(m-1) != 0 {
ans = append(ans, x)
}
}
return ans
}class Solution {
public:
vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
unordered_map<int, int> mask;
auto add = [&](vector<int>& nums, int bit) {
unordered_set<int> seen(nums.begin(), nums.end());
for (int x : seen) {
mask[x] |= bit;
}
};
add(nums1, 1);
add(nums2, 2);
add(nums3, 4);
vector<int> ans;
for (auto& [x, m] : mask) {
if ((m & (m - 1)) != 0) {
ans.push_back(x);
}
}
return ans;
}
};class Solution:
def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
mask = {}
for x in set(nums1):
mask[x] = mask.get(x, 0) | 1
for x in set(nums2):
mask[x] = mask.get(x, 0) | 2
for x in set(nums3):
mask[x] = mask.get(x, 0) | 4
return [x for x, m in mask.items() if m & (m - 1)]var twoOutOfThree = function(nums1, nums2, nums3) {
const mask = new Map();
const add = (nums, bit) => {
const seen = new Set(nums);
for (const x of seen) {
mask.set(x, (mask.get(x) || 0) | bit);
}
};
add(nums1, 1);
add(nums2, 2);
add(nums3, 4);
const ans = [];
for (const [x, m] of mask.entries()) {
if ((m & (m - 1)) !== 0) {
ans.push(x);
}
}
return ans;
};中文
题目概述
给定三个整数数组 nums1、nums2、nums3，返回所有至少出现在其中两个数组里的不同整数。返回顺序任意。
核心思路
同一个数组内的重复元素只能算该数组出现一次，因此要先“按数组去重”，再统计每个值出现于哪些数组。可用 3 位掩码表示：1 代表 nums1，2 代表 nums2，4 代表 nums3。
算法步骤
- 分别把三个数组转成集合，去除数组内重复。
- 遍历 set1/set2/set3，分别给对应值的掩码按位或 1/2/4。
- 最后检查每个值的掩码，若至少有两位为 1，则加入答案。
- 判断“至少两位为 1”可用：(m & (m - 1)) != 0。
复杂度分析
设总元素个数为 n。
时间复杂度：O(n)（平均）。
空间复杂度：O(n)。
常见陷阱
- 没有先按数组去重，导致同数组重复值被重复计数。
- 把“至少出现在两个数组”误写成“总出现次数至少两次”。
- 误以为输出需要固定顺序（题目允许任意顺序）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
Map<Integer, Integer> mask = new HashMap<>();
Set<Integer> s1 = new HashSet<>();
for (int x : nums1) s1.add(x);
for (int x : s1) mask.put(x, mask.getOrDefault(x, 0) | 1);
Set<Integer> s2 = new HashSet<>();
for (int x : nums2) s2.add(x);
for (int x : s2) mask.put(x, mask.getOrDefault(x, 0) | 2);
Set<Integer> s3 = new HashSet<>();
for (int x : nums3) s3.add(x);
for (int x : s3) mask.put(x, mask.getOrDefault(x, 0) | 4);
List<Integer> ans = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : mask.entrySet()) {
int m = e.getValue();
if ((m & (m - 1)) != 0) {
ans.add(e.getKey());
}
}
return ans;
}
}func twoOutOfThree(nums1 []int, nums2 []int, nums3 []int) []int {
mask := map[int]int{}
add := func(nums []int, bit int) {
seen := map[int]bool{}
for _, x := range nums {
if !seen[x] {
seen[x] = true
mask[x] |= bit
}
}
}
add(nums1, 1)
add(nums2, 2)
add(nums3, 4)
ans := make([]int, 0)
for x, m := range mask {
if m&(m-1) != 0 {
ans = append(ans, x)
}
}
return ans
}class Solution {
public:
vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
unordered_map<int, int> mask;
auto add = [&](vector<int>& nums, int bit) {
unordered_set<int> seen(nums.begin(), nums.end());
for (int x : seen) {
mask[x] |= bit;
}
};
add(nums1, 1);
add(nums2, 2);
add(nums3, 4);
vector<int> ans;
for (auto& [x, m] : mask) {
if ((m & (m - 1)) != 0) {
ans.push_back(x);
}
}
return ans;
}
};class Solution:
def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
mask = {}
for x in set(nums1):
mask[x] = mask.get(x, 0) | 1
for x in set(nums2):
mask[x] = mask.get(x, 0) | 2
for x in set(nums3):
mask[x] = mask.get(x, 0) | 4
return [x for x, m in mask.items() if m & (m - 1)]var twoOutOfThree = function(nums1, nums2, nums3) {
const mask = new Map();
const add = (nums, bit) => {
const seen = new Set(nums);
for (const x of seen) {
mask.set(x, (mask.get(x) || 0) | bit);
}
};
add(nums1, 1);
add(nums2, 2);
add(nums3, 4);
const ans = [];
for (const [x, m] of mask.entries()) {
if ((m & (m - 1)) !== 0) {
ans.push(x);
}
}
return ans;
};
Comments