如何在一个数组中找到两个元素的和为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]+"}");  
}  

- AKIWEB

---

可能是重复的问题：给定两个数组a和b，找到所有满足a1属于数组A且b1属于数组B的元素对(a1,b1)，使得它们的和a1+b1=k。 - user180100

查找数组中两个元素的和为k：参见https://dev59.com/FlbTa4cB1Zd3GeqP7yB4 - user180100

在你的例子中，你假设这两个整数是相邻的。这是故意的吗？对于k=6，如果A={2,3,4}，即使{2,4}=6，也不会返回任何东西。此外，你的算法是O(n)，因此不能编写更有效的算法，但可以编写更正确的算法。 - kba

Answer 1

如果输入数组中存储的数字仅为正数，则我会创建另一个数组K，其中包含k + 1个ArrayList元素。其中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+".");
        }
    }

}

- Mr1159pm

---

感谢详细的解答。在这个数组输入 {6,4,5,1,4,2,0} 中，我得到的答案是 索引为 [6, 0] 的数字相加等于6。 索引为 [3, 2] 的数字相加等于6。 索引为 [5, 1] 的数字相加等于6。 索引为 [5, 4] 的数字相加等于6。 是否有什么问题？ - AKIWEB

这些是索引，而不是值。你的数组索引是从零开始的，所以索引为5的项是整数2，索引为4的项是整数4，所以2+4等于6。一切看起来都很好。你可以将println语句转换为打印值而不是索引，但是索引更有用（在我看来），因为你可以在许多不同的索引中拥有相同的数字。 - Mr1159pm

Answer 2

public static void main(String[] args) {
    // TODO Auto-generated method stub

    int arr[]={4,2,6,8,9,3,1};
    int sum=10;
    int arr1[]=new int[sum];


    for(int x=0;x<arr.length;x++)
    {
        arr1[arr[x]]++;
    }

    for(int y=0;y<arr.length;y++)
    {
        if(arr1[sum-arr[y]]==1)
        {
            System.out.println(arr[y]+","+(sum-arr[y]));
        }
    }

}

- Bharath Kumar

---

你能否提供一些关于如何回答问题或更有效的解释？ - Mogsdad

Answer 3

与您的另一个问题一样，O(log n)是不可能的，因为您必须检查整个数组。但是O(n)更或多或少是可能的。

如果您的可能整数范围相对较小 - 也就是说，如果它在常数因子n内 - 那么您可以编写：

final boolean[] seen = new boolean[max - min + 1];
for(final int a : A)
{
    if(seen[input - a - min])
        System.out.println("{" + (input - a) + "," + a + "}");
    seen[a - min] = true;
}

如果不想使用数组，你可以使用一个 HashSet<Integer> 来实现同样的功能：

final Set<Integer> seen = new HashSet<Integer>();
for(final int a : A)
{
    if(seen.contains(input - a))
        System.out.println("{" + (input - a) + "," + a + "}");
    seen.add(a);
}

但这并不能保证 O(n) 的时间复杂度。

- ruakh

---

你能解释一下HashSet方法的问题吗？因为你说它不能保证O(n)时间。 - AKIWEB

Answer 4

关于这个问题，我的小答案是使用O(n)的时间复杂度和O(n)的额外内存。这段代码片段返回所有元素和为K的唯一索引对。

/**
 * Returns indices of all complementary pairs in given {@code arr} with factor {@code k}. Two elements {@code arr[i]} and {@code arr[j]} are
 * complementary if {@code arr[i] + arr[j] = k}.
 * Method returns set of pairs in format {@literal [i,j]}. Two pairs {@literal [i,j]} and {@literal [j,i]} are treated as same, and only one pair
 * is returned.
 * Method support negative numbers in the {@code arr}, as wel as negative {@code k}.
 * <p>
 * Complexity of this method is <t>O(n)</t>, requires <t>O(n)</t> additional memory.
 *
 * @param arr source array
 * @param k   factor number
 * @return not {@code null} set of all complementary pairs in format {@literal [i,j]}
 */
public static Set<String> getComplementaryPairs(int[] arr, int k) {
    if (arr == null || arr.length == 0)
        return Collections.emptySet();

    Map<Integer, Set<Integer>> indices = new TreeMap<>();

    for (int i = 0; i < arr.length; i++) {
        if (!indices.containsKey(arr[i]))
            indices.put(arr[i], new TreeSet<>());
        indices.get(arr[i]).add(i);
    }

    Set<String> res = new LinkedHashSet<>();

    for (Map.Entry<Integer, Set<Integer>> entry : indices.entrySet()) {
        int x = entry.getKey();
        int y = k - x;

        if (x == y) {
            int size = entry.getValue().size();

            if (size < 2)
                continue;

            Integer[] ind = entry.getValue().toArray(new Integer[size]);

            for (int j = 0; j < size - 1; j++)
                for (int m = j + 1; m < size; m++)
                    res.add(String.format("[%d,%d]", ind[j], ind[m]));
        } else if (x < y && indices.containsKey(y))
            for (int j : entry.getValue())
                for (int m : indices.get(y))
                    res.add(String.format("[%d,%d]", j, m));
    }

    return res;
}

- oleg.cherednik