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. 代码实现

package lc2657;

import java.util.HashMap;

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int count = 0;
        int[] res = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 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;
        }
        return res;
    }
}

4. 代码优化说明

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

class Solution {
public int[] findThePrefixCommonArray(int[] A, int[] B) {
int n = A.length;
int[] res = new int[n];
int[] count = new int[n + 1];
int common = 0;

        for (int i = 0; i < n; i++) {
            if (++count[A[i]] == 2) common++;
            if (++count[B[i]] == 2) common++;
            
            res[i] = common;
        }
        return res;
    }
}

5. 复杂度分析

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

6. 总结

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