C程序双指针技术

双指针确实是一种简单而有效的技术，通常用于搜索排序数组中的配对。
给定一个有N个整数的排序数组A（按升序排序），求是否存在任何一对元素（A[i], A[j]），使其总和等于X。

让我们看看这个原生的解决方案。

// Naive solution to find if there is a
// pair in A[0..N-1] with given sum.
#include <stdio.h>
  
int isPairSum(int A[],int  N,int X)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) 
        {
            // as equal i and j means same element
            if (i == j) 
                continue;
            
            // pair exists
            if (A[i] + A[j] == X)
                return true; 
  
            // as the array is sorted
            if (A[i] + A[j] > X)
                break; 
        }
    }
  
    // No pair found with given sum.
    return 0;
}
  
// Driver Code
int main()
{
    int arr[]={3,5,9,2,8,10,11};
    int val=17;
    int arrSize = sizeof(arr)/sizeof(arr[0]);
    
    // Function call
    printf("%d",isPairSum(arr,arrSize,val));
  
    return 0;
}

输出

时间复杂度： O(n 2)。

现在我们来看看双指针技术是如何工作的。我们取两个指针，一个代表数组的第一个元素，另一个代表数组的最后一个元素，然后我们将两个指针上的值相加。如果它们的总和小于X，那么我们就把左边的指针移到右边，如果它们的总和大于X，那么我们就把右边的指针移到左边，以便更接近总和。我们继续移动指针，直到我们得到的总和为X。

#include <stdio.h>
  
// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
int isPairSum(int A[], int N, int X)
{
    // represents first pointer
    int i = 0;
  
    // represents second pointer
    int j = N - 1;
  
    while (i < j)
    {
        // If we find a pair
        if (A[i] + A[j] == X)
            return 1;
  
        // If sum of elements at current
        // pointers is less, we move towards
        // higher values by doing i++
        else if (A[i] + A[j] < X)
            i++;
  
        // If sum of elements at current
        // pointers is more, we move towards
        // lower values by doing j--
        else
            j--;
    }
    return 0;
}
  
// Driver code
int main()
{
    // array declaration
    int arr[] = { 3, 5, 9, 2, 8, 10, 11 };
      
    // value to search
    int val = 17;
      
    // size of the array
    int arrSize = sizeof(arr) / sizeof(arr[0]);
    
    // Function call
    printf("%d", isPairSum(arr, arrSize, val));
  
    return 0;
}