相关疑难解决方法(0)

给定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] …

问题:给定一个未排序的正整数数组,是否有可能从该数组中找到一对总和达到给定总和的整数？

约束:这应该在O(n)和就地(没有任何外部存储,如数组,哈希映射)完成(你可以使用额外的变量/指针)

如果这是不可能的,那么可以给出相同的证明吗？

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