題目:

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.

給定兩個陣列,回傳裡面有兩陣列重疊元素的陣列,且該陣列不能有重複元素
ex:input:nums1=[1,2,2,1],nums2=[2,2]=>output:[2]

簡單來說就是找出兩陣列重複值的set

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans=[]
        for i in nums1:
            if i in nums2 and i not in ans:
                ans.append(i)
        return ans

遍歷nums1,找出其中在nums2內且尚未被記錄的元素
將其紀錄至ans,最後回傳ans
最後執行時間63ms(faster than 71.99%)

這個方法感覺有點太慢,所以我又改採用雙指標的方法

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        
        l,r=0,0
        ans = []
        while l <len(nums1) and r <len(nums2):
            if nums1[l]<nums2[r]:
                l=l+1
            elif nums2[r] <nums1[l]:
                r=r+1
            else:
                if nums1[l] not in ans:
                    ans.append(nums1[l])
                r=r+1
                l=l+1
        return ans

先將兩陣列排序,設立兩個指標(l,r)
一個從nums1頭,一個從nums2頭開始走
若l位置的值小於r位置的值,l往前走
若l位置的值大於r位置的值,r往前走
若l位置的值等於r位置的值且該值未被記錄,則於ans紀錄該值
直到其中一個指標走到底回傳ans
最後執行時間50ms(faster than 90.96%)

而討論區有人則是直接拿出set的內建函式來實作

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return set(nums1).intersection(set(nums2))

將兩陣列變為set,回傳它們的交集
最後執行時間40ms(faster than 99.31%)

那我們下題見