如何将时间复杂度从 O(n^2) 降低到 O(n)

Question

我最近参加了一次面试，他们要求我使用时间复杂度来解决以下问题O(n)。（黑客排名）

问题：

给定一个整数数组，就会有l整数和r整数。需要找到哪些所有元素对的总和相等并且介于 和l之间r；

例子：

int[] array = {2,3,4,5}; int l=5, int r=7;

输出：4

输入属性：

• 输入未排序。
• 输入将包含重复的元素。
• 输入数组是非负的。

下面的组合将返回相等且在范围值之间的总和l，r如果该对小于l或大于r则应跳过。而且配对不能重复：

array[0] + array[1] = 5 -> counter++
array[0] + array[2] = 6 -> counter++
array[0] + array[3] = 7 -> counter++
array[1] + array[2] = 7 -> counter++
array[1] + array[3] = 8 -> greater than r, no counter increment

我尝试了以下方法，效果很好，但时间复杂度为 O(n^2)：

 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;
    }

有人可以帮我找到一种方法来优化上述代码以提高O(n)时间复杂度吗？

Answer 1

这是我使用累积直方图而不是排序的方法。在 C++ 中，抱歉。

static int sumPairsLinear(int *pArray,int iArraySize, int l, int r)
{
    int iResult = 0;
    // 1. Iterate the array and toss any entries larger than r
    for (int i=0;i<iArraySize;)
    {
        if (pArray[i] > r)
            pArray[i] = pArray[--iArraySize];
        else
            i++;
    }
    // 2. Allocate a zero initialised array of ints, of size `r+1`.
    int *pHistogram = new int[r+1];
    memset(pHistogram, 0, sizeof(int)*(r+1));
    // 3. Fill the histogram
    for (int i=0;i<iArraySize;i++)
    {
        pHistogram[pArray[i]]++;
    }
    // 4. Convert it to a cumulative histogram. 
    for (int i=1;i<=r;i++)
    {
        pHistogram[i] += pHistogram[i-1];
    }
    // 5. Iterate through the values again. Use the cumulative histogram to calculate the number of valid pairs.
    for (int i=0;i<iArraySize;i++)
    {
        int iVal = pArray[i];
        int iIndex = l-iVal-1;
        iResult += pHistogram[r-iVal] - ((iIndex >= 0) ? pHistogram[iIndex] : 0);
        // Don't pair with self
        iVal *= 2;
        if (iVal <= r &&
            iVal >= l)
        {
            iResult--;
        }
    }
    // 6. Half iResult because we counted each pair twice.
    iResult /= 2;

    delete[] pHistogram;
    return iResult;
}

r如果很大，但在其他方面是合理的，并且仍然是 O(N)，那么性能会很糟糕。