查找排序数组中其他两个数字之和的数字

Question

正如在主题中所述，我必须检查是否有一个数字是排序数组中的其他两个数字的总和。

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

现在，我不明白如何构建最有效的算法来做同样的事情，但有一个排序的数组。

数字的类型为int（负值或正值），并且任何数字都可以多次出现。

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

Answer 1

在这里，我用C做：

数组A [] n个数和另一个数x，判断是否存在处于S，其和精确的x两个元素。

方法1（使用分选）

算法：

hasArrayTwoCandidates（A []​​，ar_size，总和） 1）排序在非递减次序排列。

2）初始化两个索引变量以查找排序数组中的候选元素。

（a）首先初始化到最左边的索引：L = 0

（B）初始化第二最右边的索引：R = ar_size-1

3）循环而升<河

（a）若（A [1] + A [R] ==总和），则返回1

（B）否则如果（A [1] + A [R] <总和）然后升++

（C）否则R--

4）在整个阵列没有候选 - 返回0

实施例： 让阵列是{1，4，45，6，10，-8}总和找到是16

排序阵列 A = {-8，1，4，6，10，45}

初始化L = 0，R = 5

A [1] + A [R]（-8 + 45）> 16 =>递减r。现在r = 10

A [1] + A [r]（-8 + 10）< 2 =>增量l。现在l = 1

A [1] + A [r]（1 + 10）< 16 =>增量l。现在l = 2

A [1] + A [r]（4 + 10）< 14 =>增量l。现在L = 3

A [1] + A [R]（6 + 10）== 16 =>实测值候选（返回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返回搜索关键字的索引，否则返回-1。 尺寸是阵列尺寸

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