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时说明是公共元素。算法步骤遍历每个下标i。依次把A[i]和B[i]加入统计。每次加入后检查计数是否为 2若是则公共数1。把当前公共数存入结果数组。3. 代码实现packagelc2657;importjava.util.HashMap;classSolution{publicint[]findThePrefixCommonArray(int[]A,int[]B){intnA.length;intcount0;int[]resnewint[n];HashMapInteger,IntegermapnewHashMap();for(inti0;in;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){intnA.length;int[]resnewint[n];int[]countnewint[n1];intcommon0;for(inti0;in;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. 总结核心思路计数统计 一次遍历。关键元素出现两次即为公共元素直接计数即可。优化版用数组替代哈希表速度更快、代码更短。