java - 如何在数组中找到总和为 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}。 然后我会遍历输入数组的所有元素，对于每个小于或等于 k ​​的 int m，我会获取它的索引并将该索引添加到 ArrayList K 数组的索引 m 处。 然后我将遍历数组 K 的前半部分，对于其中存储了一些整数的每个索引 i，我将找到互补索引 [k-i] 并查看其中是否有任何值。如果有，那么这些就是你的对。 顺便说一句，这是 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+".");
        }
    }

}