LeetCode 每日一题笔记 日期：2026.05.20 题目：2657. 找到前缀公共数组

LeetCode 每日一题笔记

0. 前言

• 日期：2026.05.20
• 题目：2657. 找到前缀公共数组
• 难度：中等
• 标签：数组、哈希表、计数

1. 题目理解

问题描述：
给你两个长度为n、下标从0开始的整数数组A和B。
定义前缀公共数组C为：C[i]等于数组A和B中下标从0到i的部分中公共元素的个数。
返回前缀公共数组C。

示例：

输入：A = [1,3,2,4], B = [3,1,2,4]
输出：[0,2,3,4]

2. 解题思路

核心观察

• 一个数字成为公共元素，当且仅当它在A和B的前i项中各出现一次。
• 用计数/哈希表统计每个数字出现次数，次数达到 2时，说明是公共元素。

算法步骤

1. 遍历每个下标i。
2. 依次把A[i]和B[i]加入统计。
3. 每次加入后检查计数是否为 2，若是则公共数+1。
4. 把当前公共数存入结果数组。

3. 代码实现

packagelc2657;importjava.util.HashMap;classSolution{publicint[]findThePrefixCommonArray(int[]A,int[]B){intn=A.length;intcount=0;int[]res=newint[n];HashMap<Integer,Integer>map=newHashMap<>();for(inti=0;i<n;i++){map.computeIfAbsent(A[i],k->0);map.put(A[i],map.get(A[i])+1);if(map.get(A[i])==2){map.put(A[i],0);count++;}map.computeIfAbsent(B[i],k->0);map.put(B[i],map.get(B[i])+1);if(map.get(B[i])==2){map.put(B[i],0);count++;}res[i]=count;}returnres;}}

4. 代码优化说明

减少if分支判断，用数组替代哈希表更快更简洁：

classSolution{publicint[]findThePrefixCommonArray(int[]A,int[]B){intn=A.length;int[]res=newint[n];int[]count=newint[n+1];intcommon=0;for(inti=0;i<n;i++){if(++count[A[i]]==2)common++;if(++count[B[i]]==2)common++;res[i]=common;}returnres;}}

5. 复杂度分析

• 时间复杂度：O(n)O(n)O(n)
  一次遍历完成所有统计与赋值。
• 空间复杂度：O(n)O(n)O(n)
  使用计数数组/哈希表存储元素出现次数。

6. 总结

• 核心思路：计数统计 + 一次遍历。
• 关键：元素出现两次即为公共元素，直接计数即可。
• 优化版用数组替代哈希表，速度更快、代码更短。