Contents

[Golang][Leetcode][HashTable]刷題系列-349-數組交集


349. Intersection of Two Arrays


Level : Easy

原題連結 : Click

題目 :

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.


Example :

Note

Input: nums1 = [1,2,2,1], nums2 = [2,2]

Output: [2]


Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output: [9,4]

Explanation: [4,9] is also accepted.


解題思路 :

  • 題目給我們兩個數組,請我們找出兩數組的交集,若有重複element只算1個
  • 這種情況派出golang中的map結構來儲存最為直觀且好用!
  • 直接將其中一個數組放進map中,然後key為該數字,value設為1表示其出現過
  • 再用第二個數組對此map做查找,若找到(value == 1)就將其加到我們要回傳的數組中,並且將此key的value從1改設回0,這樣之後遇到重複的數字便不會再加入回傳數組中

以下是我的解法: time complexity: O(n) , space complexity: O(n)

  • 假設數組中有n個element,time complexity: O(n)
  • 隨著n的大小等比擴大它所需要的空間,space complexity: O(n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Intersection of Two Arrays.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func intersection(nums1 []int, nums2 []int) []int {
    
    var res []int
    
    intMap :=  make(map[int]int) 
    
    for _, num := range nums1 {
        
        intMap[num] = 1
        
    }
    
    for _, num := range nums2 {
        
        
        if val := intMap[num]; val == 1 {
            res = append(res,num)
            intMap[num] = 0
        }
    }
    
    return res
    
}


最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!