相关疑难解决方法(0)

我正在寻找具有最小时间和空间复杂性的以下算法的解决方案.

给定两个数组a和b,找到所有元素对(a1,b1),使得a1属于数组A,b1属于数组B,其和a1 + b1 = k(任何整数).

我能够提出O(n log n)方法,我们将其中一个数组排序为A,对于数组B中的每个元素b,对排序数组A进行二进制搜索以获得值(Kb).

我们可以进一步改进吗？

// Checks whether the array contains two elements whose sum is s.
// Input: A list of numbers and an integer s
// Output: return True if the answer is yes, else return False

public static boolean calvalue (int[] numbers, int s){
for (int i=0; i< numbers.length; i++){
    for (int j=i+1; j<numbers.length;j++){
        if (numbers[i] < s){
            if (numbers[i]+numbers[j] == s){
                return true;
                }
            }
        }
    }
    return false;
}

假设给你一个未排序整数数组：

A = {3,4,5,1,4,2}

输入6 输出 ：{5,1}, {4,2}

我怎样才能在 O(n) 或 O(log n) 内做到这一点。任何建议将不胜感激。

更新： 我们可以写一些比这更有效的东西吗？

for(int i=0;i<array.length-1;i++)  
{  
    if(array[i]+array[i+1]==6)  
        System.out.println("{"+array[i]+","+array[i+1]+"}");  
}