从数组中找到一对元素,其总和等于给定的数字

Question

给定n个整数的数组并给出数字X,找到所有唯一的元素对(a,b),其总和等于X.

以下是我的解决方案,它是O(nLog(n)+ n),但我不确定它是否是最优的.

int main(void)
{
    int arr [10] = {1,2,3,4,5,6,7,8,9,0};
    findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
    std::sort(arr, arr+len);
    int i = 0;
    int j = len -1;
    while( i < j){
        while((arr[i] + arr[j]) <= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            i++;
        }
        j--;
        while((arr[i] + arr[j]) >= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            j--;
        }
    }
}

Answer 1

该解决方案有3种方法:

总和为T,n为数组大小

方法1:
这样做的天真方法是检查所有组合(n选择2).这种详尽的搜索是O(n ²).

方法2: 
 更好的方法是对数组进行排序.这需要O(n log n)
然后对于数组A中的每个x,使用二进制搜索来查找Tx.这将需要O(nlogn).
因此,整体搜索是O(n log n)

方法3:
最好的方法是将每个元素插入到哈希表中(不进行排序).这将O(n)作为恒定时间插入.
然后对于每个x,我们可以只查找它的补码Tx,即O(1).
总的来说,这种方法的运行时间是O(n).

你可以在这里详细介绍.谢谢.

Answer 2

# Let arr be the given array.
# And K be the give sum


for i=0 to arr.length - 1 do
  hash(arr[i]) = i  // key is the element and value is its index.
end-for

for i=0 to arr.length - 1 do
  if hash(K - arr[i]) != i  // if Kth element exists and it's different then we found a pair
    print "pair i , hash(K - arr[i]) has sum K"
  end-if
end-for

Answer 3

在Java中实现:使用codaddict的算法(可能略有不同)

import java.util.HashMap;

public class ArrayPairSum {


public static void main(String[] args) {        

    int []a = {2,45,7,3,5,1,8,9};
    printSumPairs(a,10);        

}


public static void printSumPairs(int []input, int k){
    Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();

    for(int i=0;i<input.length;i++){

        if(pairs.containsKey(input[i]))
            System.out.println(input[i] +", "+ pairs.get(input[i]));
        else
            pairs.put(k-input[i], input[i]);
    }

}
}

对于input = {2,45,7,3,5,1,8,9},如果Sum为10

输出对:

3,7 
8,2
9,1

关于解决方案的一些说明:

• 我们只通过数组迭代一次 - > O(n)时间
• Hash中的插入和查找时间为O(1).
• 总时间是O(n),尽管它在散列方面使用了额外的空间.

Answer 4

java中的解决方案.您可以将所有String元素添加到字符串的ArrayList并返回列表.我在这里打印出来.

void numberPairsForSum(int[] array, int sum) {
    HashSet<Integer> set = new HashSet<Integer>();
    for (int num : array) {
        if (set.contains(sum - num)) {
            String s = num + ", " + (sum - num) + " add up to " + sum;
            System.out.println(s);
        }
        set.add(num);
    }
}