如何将数组区间和数对统计算法从O(n²)优化至O(n)？

问题说明 #

给定未排序、包含重复元素的非负整数数组，统计所有i<j的不重复数对中，两元素之和落在区间[l, r]内的数量。示例：数组{2,3,4,5}，l=5，r=7，输出为4（对应数对(2,3),(2,4),(3,4),(2,5)）。

你当前的O(n²)实现可正常运行，但面对大数据量时会超时，以下是优化思路：

原代码回顾 #

public static int sumPairs(int[] array,int l, int r)
{
    int counter=0;
    for(int i=0;i<array.length;i++)
    {
        for(int j=i+1;j<array.length;j++)
        {
            int sum = array[i]+array[j];
            
            if(sum<=r && sum>=l)
            {
                counter++;
            }
        }
    }
    
    return counter;
}

优化方案 #

核心思路 #

将问题转化为：统计两数和≤r的数对总数 减去 统计两数和≤l-1的数对总数，这样就能直接得到和在[l, r]范围内的数对数量。根据元素取值范围的不同，有两种针对性实现方式：

场景1：元素取值范围较小（如最大值≤n或可接受的规模）

利用计数数组统计频率，实现严格O(n)时间复杂度：

1. 统计频率：遍历数组，用计数数组记录每个非负整数的出现次数，时间O(n)。
2. 双指针计算符合条件的数对：
   定义辅助函数countPairsLessOrEqual，通过左右指针遍历计数数组，快速统计两数和≤k的数对数量，时间O(maxVal)（maxVal为数组元素最大值，若maxVal与n同阶则整体为O(n)）。

辅助函数实现示例：

private static long countPairsLessOrEqual(int[] count, int maxVal, int k) {
    long res = 0;
    int left = 0;
    int right = maxVal;
    while (left <= right) {
        if (left + right > k) {
            right--;
        } else {
            if (left == right) {
                // 计算从count[left]个元素中选2个的组合数
                res += (long) count[left] * (count[left] - 1) / 2;
            } else {
                // 不同元素的数对数量为两者频率的乘积
                res += (long) count[left] * count[right];
            }
            left++;
        }
    }
    return res;
}

主函数改造：

public static int sumPairs(int[] array, int l, int r) {
    if (array.length < 2) return 0;
    
    // 找出数组最大值，创建计数数组
    int maxVal = 0;
    for (int num : array) {
        if (num > maxVal) maxVal = num;
    }
    int[] count = new int[maxVal + 1];
    for (int num : array) {
        count[num]++;
    }
    
    long pairsUpToR = countPairsLessOrEqual(count, maxVal, r);
    long pairsUpToLMinus1 = countPairsLessOrEqual(count, maxVal, l - 1);
    return (int) (pairsUpToR - pairsUpToLMinus1);
}

场景2：元素取值范围极大（如1e9）

此时无法使用计数数组，最优方案是排序+双指针，时间复杂度O(n log n)（远优于O(n²)）：

1. 排序数组：O(n log n)时间。
2. 双指针统计数对：
   定义辅助函数countPairsLessOrEqual，用左右指针遍历排序后的数组，快速统计两数和≤k的数对数量，时间O(n)。

辅助函数实现示例：

private static long countPairsLessOrEqual(int[] nums, int k) {
    long res = 0;
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        if (nums[left] + nums[right] <= k) {
            // 左指针到右指针-1的所有元素与nums[left]的和都≤k
            res += right - left;
            left++;
        } else {
            right--;
        }
    }
    return res;
}

主函数改造：

import java.util.Arrays;

public static int sumPairs(int[] array, int l, int r) {
    if (array.length < 2) return 0;
    
    Arrays.sort(array);
    long pairsUpToR = countPairsLessOrEqual(array, r);
    long pairsUpToLMinus1 = countPairsLessOrEqual(array, l - 1);
    return (int) (pairsUpToR - pairsUpToLMinus1);
}

说明 #

• 场景1的严格O(n)实现依赖元素取值范围有限的前提，若元素范围极大，场景2的O(n log n)是当前最优解，也是面试中普遍认可的优化方向。
• 两种方案都避免了遍历所有i<j的数对，大幅降低了时间复杂度，适合处理大规模数据。

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