如何使这段代码更有效地找到一个和为特定值的数对？

Question

我在testdome.com上做这个有趣的测试（点击此处可查看），但未能通过效率测试。你有更好的方法吗？我没有重复计算任何值。这似乎是唯一的办法就是采用暴力方法，即n^2算法。

以下是该问题的说明:

编写一个函数，给出一个列表和一个目标总和，返回两个不同元素的下标和等于目标总和的结果。如果没有这样的元素，则应返回null。

例如，findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12) 应当返回下列任意元组的下标：

1, 4 (3 + 9 = 12), 2, 3 (5 + 7 = 12), 3, 2 (7 + 5 = 12) 或 4, 1 (9 + 3 = 12)。

下面是我的代码：

public class TwoSum {
public static int[] findTwoSum(int[] list, int sum) {
    if (list == null || list.length < 2) return null;
    for (int i = 0; i < list.length - 1; i++) { //lower indexed element
        for (int j = i + 1; j < list.length; j++) { //higher indexed element
            if (list[i] + list[j] == sum) {
                return new int[]{i, j};
            }
        }
    }

    //none found  
    return null;
}


public static void main(String[] args) {
    int[] indices = findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12);
    System.out.println(indices[0] + " " + indices[1]);
}

编辑：这是我的最终可行代码。谢谢大家！

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public static int[] findTwoSum(int[] list, int sum) {
        if (list == null || list.length < 2) return null;
        //map values to indexes
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < list.length; i++) {
            indexMap.put(list[i], i);
        }

        for (int i = 0; i < list.length; i++) {
            int needed = sum - list[i];
            if (indexMap.get(needed) != null) {
                return new int[]{i, indexMap.get(needed)};
            }
        }

        //none found
        return null;
    }

    public static void main(String[] args) {
        int[] indices = findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12);
        System.out.println(indices[0] + " " + indices[1]);
    }
}

根据Kon的建议，一次性完成以下操作：

public static int[] findTwoSum(int[] list, int sum) {
    if (list == null || list.length < 2) return null;
    //map values to indexes
    Map<Integer, Integer> indexMap = new HashMap<>();
    for (int i = 0; i < list.length; i++) {
        int needed = sum - list[i];
        if (indexMap.get(needed) != null) {
            return new int[]{i, indexMap.get(needed)};
        }

        indexMap.put(list[i], i);
    }

    //none found
    return null;
}

- yts

---

你现在正在用一种天真的方式解决问题。正如你所说，这将会在n^2 的时间内给出一个解决方案。但是有可能用线性时间得到一个解决方案。该解决方案使用了一个非常流行的数据结构。你能否想一想并取得进展？ - Kon

嗯...谢谢你的提示，我会尝试弄清楚的。 - yts

请在这里随时提出澄清问题。这是非常流行的面试问题（我自己也问过很多次），所以最好自己“发现”解决方案，这样您将更好地学习它。 - Kon

你可以使用字典吗？ - Peter de Rivaz

@Kon 给一个人一条鱼，你可以养活他一天；教一个人钓鱼，你可以养活他一辈子。 :) - yts

Answer 1

看看你在内部循环中所做的事情，你正在检查是否满足 list[i] + list[j] == sum。

如果稍微转换一下等式，这意味着在给定 list[i] 和 sum（它们都是内部循环中的常数）的情况下，你实际上正在询问“是否存在一个索引，其中存储了值（sum-list[i]）”，这就是您内部循环解决的问题。

现在应用能够在线性时间内使用类似于 indexOf(sum - list[i]) 的方法解决问题的知识，有一些数据结构可以以比 O(N) 更好的时间回答这种问题。

- Durandal

---

更新了我的问题以展示我的代码。你给了我我想要的信息量。 - yts

@yts 哇，那看起来正是我想的东西 :P 你确定你没有读到我的心思吗？很高兴你能想出来。 - Durandal

不告诉你（这是填充文本，以使我的评论长度至少为15个字符） - yts

Answer 2

这里是线性解决方案（不包括排序，排序的时间复杂度为O(n*log(n))）：
1) 对初始数组a[]进行排序
2) 令i为a[]的第一个索引，j为最后一个索引

i = 0;
j = a[].length - 1;

3) 让我们从两端开始移动：

do{
  if(a[i]+a[j] < sum)
    i++;
  else if(a[i]+a[j] > sum)
    j--;
  else { // we have found required indexes!
     put (i, j) to result set;
     i++;
  }
} while(i < j);

最终结果 - 一组满足要求的数对(i,j)。
您可以在找到第一组数对后停止并返回它。

P.S. 如果您有像{3, 3, 3, 3, 9, 9, 9, 9}这样的数组，则此解决方案将无法给出所有组合：)

- sberezin

---

嗯...看起来很有趣。我本来想说排序是n*log(n)，但你比我先说了 :) Durandal的解决方案是线性的，对我来说更直观，所以我选择了它。 - yts

Answer 3

public static Map<Integer, Integer> findTwoSum(int[] list, int sum) {
    if (list == null || list.length < 2) return null;
    Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
    Map<Integer, Integer> arrayResult = new HashMap<Integer, Integer>();
    for (int i = 0; i < list.length; i++) {
        indexMap.put(list[i], i);
    }

    for (int i = 0; i < list.length; i++) {
        int needed = sum - list[i];
        if (indexMap.get(needed) != null) {
            arrayResult.put(i, indexMap.get(needed));
        }
    }
    return arrayResult.isEmpty()?null:arrayResult;
}

public static void main(String[] args) {
    Map<Integer, Integer> indices = findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12);
    System.out.println(indices);
}

- Armando Cordova

Answer 4

这里有一个用C#编写的解决方案。将其转换为Java语言应该很容易：

static public IEnumerable<Tuple<int, int>> FindAllTwoSumIndexes(IList<int> list, long desiredSum)
{
    var count = list?.Count;
    if (list == null || count <= 1)
        return null;

    var results = new List<Tuple<int, int>>(32);
    var indexesMap = new ConcurrentDictionary<long, List<int>>(); //0 value-to-indexes
    for (var i = 0; i < count; i++)
    {
        var thisValue = list[i];
        var needed = desiredSum - thisValue;
        if (indexesMap.TryGetValue(needed, out var indexes))
        {
            results.AddRange(indexes.Select(x => Tuple.Create(x, i)));
        }

        indexesMap.AddOrUpdate(
            key: thisValue,
            addValueFactory: x => new List<int> { i },
            updateValueFactory: (x, y) =>
            {
                y.Add(i);
                return y;
            }
        );
    }

    return results.Any() ? results.OrderBy(x => x.Item1).ThenBy(x => x.Item2).ToList() : null;

    //0 bare in mind that the same value might be found over multiple indexes   we need to take this into account
    //  also note that we use concurrentdictionary not for the sake of concurrency or anything but because we like
    //  the syntax of the addorupdate method which doesnt exist in the simple dictionary
}

- XDS

Answer 5

这是一个Java程序，它使用Hashtable或Set以最高效的方式查找数组中和为k的值对。

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class ArraySumUsingSet {

public static void main(String args[]) {
   prettyPrint(getRandomArray(9), 11);
   prettyPrint(getRandomArray(10), 12);
}

/**
 * Given an array of integers finds two elements in the array whose sum is equal to n.
 * @param numbers
 * @param n
 */
public static void printPairsUsingSet(int[] numbers, int n){
    if(numbers.length < 2){
        return;
    }        
    Set set = new HashSet(numbers.length);

    for(int value : numbers){
        int target = n - value;

        // if target number is not in set then add
        if(!set.contains(target)){
            set.add(value);
        }else {
            System.out.printf("(%d, %d) %n", value, target);
        }
    }
}

/*
 * Utility method to find two elements in an array that sum to k.
 */
public static void prettyPrint(int[] random, int k){
    System.out.println("Random Integer array : " + Arrays.toString(random));
    System.out.println("Sum : " + k);
    System.out.println("pair of numbers from an array whose sum equals " + k);
    printPairsUsingSet(random, k);
}

/**
 * Utility method to return random array of Integers in a range of 0 to 15
 */
public static int[] getRandomArray(int length){
    int[] randoms = new int[length];
    for(int i=0; i<length; i++){
        randoms[i] = (int) (Math.random()*15);
    }
    return randoms;
}

}

输出

Random Integer array : [0, 14, 0, 4, 7, 8, 3, 5, 7]
Sum : 11
pair of numbers from an array whose sum equals 11
(7, 4)
(3, 8)
(7, 4)
Random Integer array : [10, 9, 5, 9, 0, 10, 2, 10, 1, 9]
Sum : 12
pair of numbers from an array whose sum equals 12
(2, 10)

- Dashmeet Singh