寻求时间复杂度O(n)的替代算法：判断整数数组是否存在重复三次的元素

你的三重循环实现时间复杂度为O(n³)，效率极低，而且代码中存在明显bug——第三层循环的循环变量写成了j++，应该是k++，这会导致逻辑错误甚至死循环。以下是几种O(n)时间复杂度的替代方案：

方案一：哈希表统计出现次数 #

利用哈希表（HashMap）遍历数组时统计每个元素的出现次数，一旦发现某个元素出现次数达到3次，直接返回true，无需遍历完整个数组。这种方法时间复杂度为O(n)，空间复杂度为O(n)，是最通用的解法。

Java实现代码：

import java.util.HashMap;
import java.util.Map;

public boolean threeEqualElements(int[] arr) {
    // 数组长度小于3时直接返回false
    if (arr == null || arr.length < 3) {
        return false;
    }
    
    Map<Integer, Integer> countMap = new HashMap<>();
    for (int num : arr) {
        // 统计当前元素出现次数，默认值为0
        int currentCount = countMap.getOrDefault(num, 0) + 1;
        countMap.put(num, currentCount);
        
        // 提前返回，优化性能
        if (currentCount >= 3) {
            return true;
        }
    }
    return false;
}

方案二：数组计数（仅适用于元素范围已知的场景） #

如果数组中的整数元素范围明确（比如限定在[-1000, 1000]），可以用数组替代哈希表，进一步降低哈希表的常数开销，时间复杂度同样为O(n)。

示例代码（假设元素范围为0到1000）：

public boolean threeEqualElements(int[] arr) {
    if (arr == null || arr.length < 3) {
        return false;
    }
    
    int[] countArr = new int[1001];
    for (int num : arr) {
        countArr[num]++;
        if (countArr[num] >= 3) {
            return true;
        }
    }
    return false;
}

注意事项 #

• 哈希表方案适用于所有整数数组场景，无需限制元素范围；
• 若追求极致空间优化，且数组允许修改，可以先排序（时间复杂度O(n log n)）再遍历找连续三个相同元素，但这种方法不符合O(n)的时间要求，仅作扩展参考。

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