在排序数组中找到一个数字，该数字是另外两个数字的总和

Question

正如主题中所说，我必须检查是否有一个数字是排序数组中另外两个数字的总和。

在问题的第一部分（对于未排序的数组）我写了一个解决方案，只做了 3 个循环并检查所有组合。

现在，我无法理解如何构建最有效的算法来执行相同的操作，但使用排序数组。

数字是 int 类型（负数或正数），任何数字都可以出现多次。

有人可以提供有关该逻辑问题的线索吗？

Answer 1

这里我用C:

n个数和另一个数x的数组A[]，判断S中是否存在两个元素之和正好为x

方法 1（使用排序）

算法：

hasArrayTwoCandidates (A[], ar_size, 求和) 1) 对数组进行非降序排序

2) 初始化两个索引变量，在排序后的数组中寻找候选元素

(a) 先初始化到最左边的索引：l = 0

(b) 初始化第二个最右边的索引：r = ar_size-1

3) 循环 while l < r.

(a) 如果 (A[l] + A[r] == 总和) 那么 return 1

(b) Else if( A[l] + A[r] < sum ) then l++

(c) 否则 r--

4) 整个数组中没有候选人 - return 0

示例： 设数组为 {1, 4, 45, 6, 10, -8} 求和为 16

对数组进行排序 A = {-8, 1, 4, 6, 10, 45}

初始化 l = 0, r = 5

A[l] + A[r] (-8 + 45) > 16 => 递减 r。现在 r = 10

A[l] + A[r] (-8 + 10) < 2 => 增加 l。现在 l = 1

A[l] + A[r] ( 1 + 10) < 16 => 增加 l。现在 l = 2

A[l] + A[r] ( 4 + 10) < 14 => 增加 l。现在 l = 3

A[l] + A[r] ( 6 + 10) == 16 => 找到候选人 (return 1)

实施：

# include <stdio.h>
# define bool int

void quickSort(int *, int, int);

bool hasArrayTwoCandidates(int A[], int arr_size, int sum)
{
    int l, r;

    /* Sort the elements */
    quickSort(A, 0, arr_size-1);

    /* Now look for the two candidates in the sorted 
       array*/
    l = 0;
    r = arr_size-1; 
    while(l < r)
    {
         if(A[l] + A[r] == sum)
              return 1; 
         else if(A[l] + A[r] < sum)
              l++;
         else // A[i] + A[j] > sum
              r--;
    }    
    return 0;
}

/* Driver program to test above function */
int main()
{
    int A[] = {1, 4, 45, 6, 10, -8};
    int n = 16;
    int arr_size = 6;

    if( hasArrayTwoCandidates(A, arr_size, n))
        printf("Array has two elements with sum 16");
    else
        printf("Array doesn't have two elements with sum 16 ");

    getchar();
    return 0;
}

/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING 
    PURPOSE */
void exchange(int *a, int *b)
{
    int temp;
    temp = *a;
    *a   = *b;
    *b   = temp;
}

int partition(int A[], int si, int ei)
{
    int x = A[ei];
    int i = (si - 1);
    int j;

    for (j = si; j <= ei - 1; j++)
    {
        if(A[j] <= x)
        {
            i++;
            exchange(&A[i], &A[j]);
        }
    }
    exchange (&A[i + 1], &A[ei]);
    return (i + 1);
}

/* Implementation of Quick Sort
A[] --> Array to be sorted
si  --> Starting index
ei  --> Ending index
*/
void quickSort(int A[], int si, int ei)
{
    int pi;    /* Partitioning index */
    if(si < ei)
    {
        pi = partition(A, si, ei);
        quickSort(A, si, pi - 1);
        quickSort(A, pi + 1, ei);
    }
}

Answer 2

这个是在Java中使用Hash Set；它是 O(n) 复杂度。

public static void findPair3ProPrint(int[] array, int sum) {
    Set<Integer> hs = new HashSet<Integer>();       
    for (int i : array) {           
        if (hs.contains(sum-i)) {
            System.out.print("(" + i + ", " + (sum-i) + ")" + " ");
        }else{
            hs.add(i);  
        }   
    }
}

Answer 3

执行此操作的一种有效方法是先使用排序，然后使用二进制搜索。

假设两个数是x和y，x+y=SUM

对于每个 x，在数组中搜索元素 SUM-x

使用合并排序对数组进行排序。

然后对数组a中的每个元素a[i]，对该元素进行二分查找(SUM-x) 这个算法应该在 O(nlgn).

在这里，binaryseacrh returns 如果找到搜索关键字的索引，否则它 returns -1。 SIZE 是数组大小

    for(int i=0;i<SIZE;i++)
      {
        int ind=binarysearch(SUM-a[i]);

        if(ind>0)
          printf("sum=%d + %d\n a[%d] + a[%d]\n"
                    ,a[i],a[ind],i,ind);
      }

在排序数组中找到一个数字，该数字是另外两个数字的总和

Finding a number that is sum of two other numbers in a sorted array

arrays

sorting

sum

find