題目:

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

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

這題和349.的差別在於回傳陣列的值可以重複
我一開始的想法是建立兩個hash map,紀錄兩陣列元素出現的次數

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        d1={}
        d2={}
        ans=[]
        for i in nums1:
            if i in d1:
                d1[i]=d1[i]+1
            else:
                d1[i]=1
                
        for i in nums2:
            if i in d2:
                d2[i]=d2[i]+1
            else:
                d2[i]=1
                
        for i in d1:
            if i in d2:
                x=min(d1[i],d2[i])
                ans=ans+[i]*x
            
        return ans

遍歷完兩個陣列取得它們的元素對次數的dictionary
若兩字典有重複的值,則在兩出現次數中取小(x)
在ans內加入x個該元素
最後回傳ans即可
最後執行時間45ms(faster than 97.94%)

這題當然也可以用雙指標下去解

class Solution:
    def intersect(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:
                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
最後執行時間44ms(faster than 98.30%)

那我們下題見