如何在数组中找到两个总和为 k 的元素

Question

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

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]+"}");  
}  

Answer 1

如果输入数组中存储的数字仅为正数，那么我将创建另一个包含 k+1 个 ArrayList 元素的数组 K。其中 k 是您需要将它们相加得到的数字。只有小于 k 的两个数字相加可以等于 k（假设我们处理正整数} 或特殊情况下的 {0,k}。然后我将迭代输入数组的所有元素，并且对于每个小于或等于的整数 m k 我会获取它的索引并将该索引添加到 ArrayList K 数组的索引 m 处。然后我将迭代数组 K 的前半部分，对于其中存储了一些整数的每个索引 i，我会找到互补索引 [ ki] 并查看其中是否有任何值。如果有，那么这些就是您的对。顺便说一句，这是 O(n)。

public static void findElemtsThatSumTo( int data[], int k){
    List arrayK[]= new List[k+1];
    for(int i=0; i<arrayK.length; i++)
        arrayK[i]= new ArrayList<Integer>();

    for(int i=0; i<data.length; i++){
        if(data[i]<=k)
            arrayK[data[i]].add(i);
    }

    for(int i=0; i<arrayK.length/2; i++){
        if(!arrayK[i].isEmpty() && !arrayK[k-i].isEmpty())
        {
            for(Object index: arrayK[i])
                for(Object otherIndex: arrayK[k-i])
                    System.out.println("Numbers at indeces ["+index.toString()+", "+otherIndex.toString()+"] add up to "+k+".");
        }
    }

}