求索引唯一且和为定值的四元组数量：是否存在O(N³)算法？

给定包含重复元素的有序整数数组，需统计索引唯一的四元组（四个不同索引对应元素之和等于给定值X）的数量，示例如下：

• 数组[10,20,30,40]、X=100时，仅存在1个四元组(0,1,2,3)；
• 数组[0,0,0,0,0]、X=0时，存在5个索引不同的四元组。

目前网络上的O(N³)解法多针对值唯一的四元组，而非索引唯一的情况。本人已掌握O(N⁴)暴力解法及O(N³logN)的三元组+二分查找解法，但未找到适用于本问题的O(N³)算法，特此询问是否存在此类算法。

已知解法 #

1. O(N⁴)暴力解法 #

int solution(int arr[], int arrSize, int X){
    int counter = 0;
    for(int i=0; i<arrSize-3; ++i)
        for(int j=i+1; j<arrSize-2; ++j)
            for(int k=j+1; k<arrSize-1; ++k)
                for(int l=k+1; l<arrSize; ++l)
                    if(arr[i] + arr[j] + arr[k] + arr[l] == X)
                        ++counter;
    return counter;
}

2. O(N³logN)三元组+二分查找解法 #

int solution(int arr[], int arrSize, int X){
    int counter = 0;
    for(int i=0; i<arrSize-3; ++i)
        for(int j=i+1; j<arrSize-2; ++j)
            for(int k=j+1; k<arrSize-1; ++k){
                int subX = X - arr[i] - arr[j] - arr[k];
                int first = binFirst(subX, arr, k+1, arrSize);
                // 二分查找返回subX在区间[k+1, arrSize)内第一次出现的位置，不存在则返回-1
                int last = binLast(subX, arr, k+1, arrSize);
                // 二分查找返回subX在区间[k+1, arrSize)内最后一次出现的位置，不存在则返回-1
                if(first != -1)
                    counter += last - first + 1;
            }
    return counter;
}

注：单纯优化重复元素计数无法将复杂度降低至O(N³)。

解答：存在适用于该问题的O(N³)算法 #

通过双指针优化三重循环的内层逻辑，可以实现O(N³)时间复杂度，同时正确统计所有索引唯一的四元组（包括重复元素场景），具体思路如下：

核心逻辑 #

固定前两个索引i < j，然后用双指针k = j+1、l = arrSize-1遍历剩余元素：

1. 计算当前四数之和current_sum = arr[i] + arr[j] + arr[k] + arr[l]；
2. 若current_sum == X：
   • 统计连续等于arr[k]的元素数量cnt_k，以及连续等于arr[l]的元素数量cnt_l；
   • 若arr[k] == arr[l]：区间内所有满足k ≤ k' < l' ≤ l的组合都有效，数量为(total * (total - 1)) / 2（total = l - k + 1）；
   • 若arr[k] != arr[l]：有效组合数为cnt_k * cnt_l；
   • 将统计值加到计数器后，跳过所有重复的arr[k]和arr[l]；
3. 若current_sum < X：右移k以增大总和；
4. 若current_sum > X：左移l以减小总和。

O(N³)双指针解法代码 #

int solution(int arr[], int arrSize, int X) {
    int counter = 0;
    for (int i = 0; i < arrSize - 3; ++i) {
        for (int j = i + 1; j < arrSize - 2; ++j) {
            int k = j + 1;
            int l = arrSize - 1;
            while (k < l) {
                // 用long long避免整数溢出
                long long current_sum = (long long)arr[i] + arr[j] + arr[k] + arr[l];
                if (current_sum == X) {
                    int cnt_k = 1;
                    // 统计连续相同的arr[k]数量
                    while (k + cnt_k < l && arr[k + cnt_k] == arr[k]) {
                        cnt_k++;
                    }
                    int cnt_l = 1;
                    // 统计连续相同的arr[l]数量
                    while (l - cnt_l > k && arr[l - cnt_l] == arr[l]) {
                        cnt_l++;
                    }
                    if (arr[k] == arr[l]) {
                        // 区间内元素总数，计算组合数C(total,2)
                        int total = l - k + 1;
                        counter += total * (total - 1) / 2;
                    } else {
                        counter += cnt_k * cnt_l;
                    }
                    // 跳过重复元素，避免重复计数
                    k += cnt_k;
                    l -= cnt_l;
                } else if (current_sum < X) {
                    k++;
                } else {
                    l--;
                }
            }
        }
    }
    return counter;
}

复杂度说明 #

外层两层循环时间复杂度为O(N²)，内层双指针遍历为O(N)，总时间复杂度为O(N³)，空间复杂度为O(1)（仅使用额外变量）。

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