题目重点：Salesforce Futureforce OA 面经给出逐位置判断同值是否在左、右出现；本文用前缀集合与后缀频次线性求解并做独立切片验证。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 相等采用整数值相等；左侧指下标严格小于 i，右侧指严格大于 i，当前位置不计入任一侧。
- 输出为 [leftBits,rightBits]，两个字符串长度均为 n，0 表示未出现、1 表示出现；空数组返回两个空串。
- 输入在内存中可一次读完；如果是单遍流且不能存储历史或未来，右侧答案必须延迟到读完后才能确定。
解题路线
- 先用 Counter 统计整数组各值总出现次数，代表当前及未来。再从左到右扫描，先把当前位置从右侧频次减掉，保证后缀只含严格更大的下标。
- 检查 value 是否在 left_seen 中得到左位，检查 right_count[value]>0 得到右位；最后将 value 加入 left_seen。循环不变量：处理下标 i 时，left_seen 恰好是 nums[:i] 的值集合，右频次在减当前值后恰好对应 nums[i+1:]。
- 每个位置只做常数次哈希查询和更新，因此不需要为每个 i 重扫两侧。若面试官禁止额外空间，须讨论值域限制或改变输入的许可，不能默称线性时间且 O(1) 空间。
手动走一遍
nums=[4,2,4,4,2]：i=0 的 4 左无右有，i=1 的 2 左无右有，i=2 的 4 左有右有，i=3 的 4 左有右无，i=4 的 2 左有右无；输出 ["00111","11100"]。若只有 [7]，返回 ["0","0"]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import Counter
def duplicate_sides(nums: list[int]) -> list[str]:
"""For each position, mark whether its value occurs before and after it."""
left_seen: set[int] = set()
right_count = Counter(nums)
left_bits: list[str] = []
right_bits: list[str] = []
for value in nums:
right_count[value] -= 1 # Exclude this position before checking the right side.
left_bits.append("1" if value in left_seen else "0")
right_bits.append("1" if right_count[value] > 0 else "0")
left_seen.add(value)
return ["".join(left_bits), "".join(right_bits)]
复杂度
n 为数组长度、u 为不同数值个数。建频次和扫描总时间 O(n)，两个哈希结构占 O(u)，输出占 O(n)。Python 哈希操作按均摊 O(1) 计；若需严格最坏界，可按排序/平衡树实现并改变复杂度。
易错点与追问
容易失分的边界
- 右频次尚含当前位置就判断，单次出现的值会被错标为右侧出现。
- 先把当前值加入 left_seen 再判断，令所有左侧位都变成 1。
- 只用 set 处理右侧，不能在扫描中正确知道最后一次出现已过；需要计数或预先计算后缀集合。
- 把返回顺序左右颠倒，或用整数位串丢失前导零。
继续深挖
- 若只需判断是否在任一侧重复，可合并两位；但仍要先定义当前位置是否计入。
- 若内存紧张且值域有限，可用定长频次数组代替哈希表；值域很大时则不合算。
- 若输入是流，怎样先存位置和总频次，再第二遍输出右侧标记？需明确是否允许落盘或两遍读取。
