数组重复元素查找算法中内层j循环从i+1起始的原理答疑

问题场景 #

为夯实数据结构与算法基础练习编程面试题（此前有照搬代码的习惯，目前正在纠正该问题），在练习搜索类算法问题时，实现了数组重复元素查找功能，可正确运行的代码如下：

arr = [1, 2, 3, 4, 3]

for i in range(0, len(arr)):
  for j in range(i+1, len(arr)):
    if arr[i] == arr[j]:
      print(arr[j])

代码运行后可正确输出结果：

3

目前存在的疑问：反复试错后才确定内层循环需要写为for j in range(i+1, len(arr))，但不清楚该写法的生效逻辑，不清楚为什么以下两种写法都会返回异常结果：

• 写法1：j从0位置开始遍历：for j in range(0, len(arr))
• 写法2：j从i位置开始遍历：for j in range(i, len(arr))

逻辑拆解 #

这个边界写法的核心作用是既避免元素和自身比对的误判，又跳过无意义的重复比较，保证每一次比对都是两个不同位置的元素，且所有元素对仅比对一次，三种写法的实际运行差异如下：

• 若使用for j in range(0, len(arr))让j从0开始遍历：
  第一，当j遍历到和i相同的索引位置时，本质是拿同一个位置的元素和自己做相等判断，不管数组有没有重复值，这个判断都一定成立，会直接把当前元素误判为重复值。比如用无重复数组[1,2,3]测试，i=0、j=0时就会错误输出1，i=1、j=1时错误输出2，结果完全不符合预期。
  第二，j遍历i之前的索引位置时，做的全是重复计算：比如i=2时，j=0、1对应的元素，早在i=0、i=1的外层循环中就已经和i=2位置的元素比对过，没有任何重复比对的必要。
• 若使用for j in range(i, len(arr))让j从i位置开始遍历：
  这个写法虽然跳过了i之前位置的重复计算，但没有避开j=i的自比场景，内层循环第一轮j就等于i，依然会触发同位置元素相等的误判。比如测试示例数组时，i=0、j=0就会错误输出1，无法得到正确结果。
• 若使用for j in range(i+1, len(arr))让j从i+1位置开始遍历：
  这个边界刚好规避了上述两个问题：j从i的下一个位置起步，首先就跳过了j=i的自比场景，不会出现误判；其次j的遍历范围始终是i位置之后还未和i做过比对的元素，所有不同位置的元素对只会被比对一次，既不会漏判重复值，也不会做多余计算，自然可以返回正确结果。

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