今日题目

https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays/description/

思路

本题中，答案加一的情况只有以下三种：

  1. $A[i] == B[i]$。
  2. $A[i]$ 出现在 $B$ 中。
  3. $B[i]$ 出现在 $A$ 中。

方法

  • 遍历数组，依次检查上述三种情况。
  • 注意情况 1 与情况 2、3 互斥。
  • 即若 cnt 已通过情况 1 加一，则情况 2、3 不会再使 cnt 增加。
  • 但情况 2 与情况 3 可以同时使 cnt 增加。

复杂度

  • 时间复杂度：$O(N)$，N 为数组长度。

  • 空间复杂度：$O(N)$，因为需要存储一个集合。

代码

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        ans = []
        cntA = set([])
        cntB = set([])
        cnt = 0
        for i in range(len(A)):
            
            if A[i] == B[i]:
                cnt += 1
            else:
                if A[i] in cntB:
                    cnt += 1
                if B[i] in cntA:
                    cnt += 1
                cntA.add(A[i])
                cntB.add(B[i])
                
            ans.append(cnt)

        return ans