关于GeeksforGeeks两数和不同对计数代码的时间复杂度求证

我并非计算机专业出身，正在学习相关知识，想确认对「统计和为指定值的不同数对」问题双指针解法的时间复杂度理解：已知Array.Sort(arr)的平均时间复杂度为O(nlogn)，但不确定代码中嵌套while循环的时间复杂度，猜测这部分是O(n)但不会证明，特来求解。

我能理解单while循环或基于哑索引的嵌套while循环的复杂度，但从未遇到过内层循环条件与外层基本一致且会修改外层循环变量的情况。

附上对应的C#代码：

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to count distinct pairs in array whose sum equal to K
static int cntDisPairs(int []arr,int N, int K)
{
     
    int cntPairs = 0;              // Stores count of distinct pairs whose sum equal to K
    Array.Sort(arr);              // Sort the array
    int i = 0;           // Stores index of the left pointer  
    int j = N - 1;      // Stores index of the right pointer
 
    // Calculate count of distinct pairs whose sum equal to K
    while (i < j) 
    {
        if (arr[i] + arr[j] == K)  // test if sum of current pair is equal to K
        {
            while (i < j && arr[i] == arr[i + 1])   // traverse to avoid consecutive duplicate array elements
            {
                i++; 
            }
 

            while (i < j && arr[j] == arr[j - 1])    // traverse to avoid consecutive duplicate array elements
            {
                j--; 
            }

            cntPairs += 1;      // Update cntPairs
            i++;
            j--;
        }
        else if (arr[i] + arr[j] < K)               // test if the sum of current pair less than K
        {
            i++;
        }
        else
        {
            j--; 
        }
    }
    return cntPairs;
}
 
public static void Main(String[] args)
{
    int[] arr = {0, 0, 300, 400, 50, 50, 500, 600, 700};
    int N = arr.Length;
    int K = 100;
     
    Console.WriteLine(cntDisPairs(arr, N, K));
}
}

时间复杂度证明 #

你对双指针部分时间复杂度为O(n)的猜测是正确的，证明核心在于指针的单向移动特性：

1. 指针移动的不可逆性：
   左指针i只会向右移动（每次i++），右指针j只会向左移动（每次j--），两者都不会回溯到之前的位置。初始时i=0，j=N-1，i的最大移动范围是从0到N-1，j的最大移动范围是从N-1到0。

2. 总移动次数的上限：
   不管是外层循环的单次移动，还是内层循环的批量移动，i和j的总移动次数之和不会超过2N（极端情况下i从0移到N-1，j从N-1移到0），这是一个线性量级的数值，因此整个双指针逻辑的时间复杂度为O(n)。

3. 分场景验证：

   • 当没有任何数对的和等于K时：内层循环完全不执行，外层循环每次仅移动i或j，最多执行N次左右，时间复杂度O(n)。
   • 当存在符合条件的数对时：内层循环的作用是跳过重复元素，本质是一次性将i或j移动到下一个不同元素的位置，这部分移动次数依然被计入i和j的总移动次数中，不会额外增加量级——比如i从当前位置一次性跳3步到下一个不同元素，这3步移动只是把原本需要3次外层循环的操作合并完成，总次数仍在O(n)范围内。

算法整体时间复杂度 #

由于排序操作的时间复杂度是O(nlogn)，远高于双指针部分的O(n)，因此整个算法的时间复杂度由排序主导，为O(nlogn)。

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