同时校验和与乘积能否判定1~N数组不存在重复元素

问题前提 #

我们的讨论对象满足以下约束：

• 数组长度为N，所有元素取值范围为1~N
• 验证目标为检测数组是否存在重复元素
• 本次仅讨论「总和校验+N!乘积校验」的组合方案本身，不涉及其他更高效的数组判重算法

已被证伪的单维度校验方案 #

此前提出的两种单独校验逻辑均已确认存在漏判：

• 方案1：仅校验数组元素总和是否等于1~N的累加和（即N*(N+1)/2）

  反例：N=4时数组[1,1,4,4]，总和为10，与1+2+3+4的计算结果相等，但数组存在明显重复元素。

• 方案2：仅校验数组元素乘积是否等于N的阶乘N!

  反例：N=4时数组[2,2,3,2]，乘积为24，与4! = 24的计算结果相等，但数组存在明显重复元素。

组合校验规则 #

提出的优化方案为同时执行上述两项校验，任意一项校验不通过则直接判定数组存在重复元素，需要验证的核心问题是：是否存在携带重复元素的数组，可以同时通过两项校验，造成漏判？

验证结论 #

该组合方案存在明确漏判问题，可构造出符合要求的反例。
以N=9的场景为例：

1. 无重复的基准数组为[1,2,3,4,5,6,7,8,9]，总和为45，乘积为9! = 362880
2. 将基准数组中的三个不同元素3、6、8（和为17，乘积为144）替换为两个4和一个9（和为4+4+9=17，乘积为449=144），得到测试数组[1,2,4,4,4,5,7,9,9]
3. 计算测试数组的参数：
   • 总和：1+2+4+4+4+5+7+9+9 = 45，与基准总和一致
   • 乘积：124445799 = 362880，与9!一致
4. 该测试数组存在三个4、两个9的重复元素，缺失3、6、8三个数，却可以同时通过两项校验，直接证明组合方案存在漏判。

这类漏判案例的构造逻辑非常清晰：只要能找到两组长度相同的1~N范围内的整数，一组全为不同值、另一组存在重复值，且两组的和相等、乘积相等，就可以通过元素替换构造出能绕过校验的重复数组。随着N的取值增大，可构造的漏判案例会越来越多。

内容的提问来源于stack exchange，提问作者Majd Odeh