LeetCode 日記 #013: 2215. Find the Difference of Two Arrays｜HashSet｜求兩個完全不同元素的兩個列表

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
answer[1] is a list of all distinct integers in nums2 which are not present in nums1.
Note that the integers in the lists may be returned in any order.

Example 1:
Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums1. Therefore, answer[1] = [4,6].

Example 2:
Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

題解

思路一

1. 先把題目給的兩個陣列轉成 Set，可以直接去重，且題目不要求排序。
2. 再用其中一個 Set 初始化一個裝共同元素的 Set，用 retainAll() 求共同元素。
3. 用 removeAll() 移除兩個 Set 裡的共同元素。
4. 初始答案列表並加入。

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Set<Integer> set1 = Arrays.stream(nums1)
                                    .boxed()
                                    .collect(Collectors.toSet());
        
        Set<Integer> set2 = Arrays.stream(nums2)
                                    .boxed()
                                    .collect(Collectors.toSet());
        
        

        Set<Integer> commonSet = new HashSet<>(set1);
        commonSet.retainAll(set2);
        set1.removeAll(commonSet);
        set2.removeAll(commonSet);

        List<List<Integer>> answer = new ArrayList<>();
        answer.add(new ArrayList<>(set1));
        answer.add(new ArrayList<>(set2));

        return answer;
    }
}

思路二

用 for 迴圈取代 Stream API 的方式會比較高效，但思路基本沒變：

1. 先用 Set 裝陣列元素，直接去重。
2. 迭代 Set 判斷有沒有跟另一個 Set 重複的元素。
3. 沒有的話存入列表內。
4. 把列表存入答案列表。

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        
        for (int num : nums1) {
            set1.add(num);
        }

        for (int num : nums2) {
            set2.add(num);
        }
        
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        
        for (int num : set1) {
            if (!set2.contains(num)) {
                list1.add(num);
            }
        }

        for (int num : set2) {
            if (!set1.contains(num)) {
                list2.add(num);
            }
        }

        List<List<Integer>> answer = new ArrayList<>();
        answer.add(list1);
        answer.add(list2);
        return answer;
    }
}