logo标签列表

如何编写一个算法来检查数组/列表中任意两个数字的和是否等于给定的数字？

algorithmlanguage-agnostic
25
如何编写一个算法，在nlogn的复杂度下检查数组/列表中任意两个数的和是否等于给定的数字？
2
你期望什么作为输出？数字？它们的索引？如果有多个结果可能会怎样？ - Marcel
1
你想要一个真/假回答即“是的，有一对”还是你想要所有的配对呢？或者你想要所有可能的组合以得到所需的总和？ - bjornhol
14个回答
33

我相信有更好的方法，但这里提供一个想法：

  1. 对数组进行排序
  2. 对于数组中的每个元素 e，二分查找其补数 (sum - e)

这两个操作的时间复杂度均为 O(n log n)。

4
排序后，丢弃所有大于总和的数字。我假设你拥有所有正整数。 - Jack
是啊，我也是这么想的，然后我忙着计算复杂度了，从没想过这两个操作都是O(nlogn)。 - Bunny Rabbit
1
你其实不需要搜索每个元素。由于你已经对数组进行了排序，在 sum/2 处停止搜索即可（虽然不影响大 O，但还是:p）。 - Matthieu M.
28

使用哈希表可以在 O(n) 的时间复杂度内完成。首先将数组中的所有数字作为键，频率作为值初始化哈希表。遍历数组中的每个数字，并检查是否存在于表中的 (sum - number)。如果存在，则表示找到了一对匹配的数字。当你遍历完数组中的所有数字后，你就会得到一个列表，其中包含所有相加得到所需数字的数字对。

array = initial array
table = hash(array)
S = sum

for each n in array
    if table[S-n] exists
        print "found numbers" n, S-n

当n和table[S-n]两次引用同一个数字的情况可以通过额外的检查来处理，但复杂度仍然是O(n)。

1
这应该是接受的答案，因为它是 O(n)，而被接受的答案是 O(n logn)。 - justinhj
除非作者能够解释他提出的解决方案如何处理非不同输入集，否则不应将其接受为最佳答案。（如果最初随机化套件中的某些数字是彼此的重复项，该怎么办）？ - Jim Dennis
哈希表中的值将表示数字在列表中出现的次数。这将允许处理重复项。 - Anurag
21

使用 哈希表。将每个数字与其索引一起插入到哈希表中。然后，设 S 是您想要的总和。对于初始数组中的每个数字 array[i]，查看是否存在具有不同于 i 的索引的值 S - array[i] 在您的哈希表中。

平均情况下为 O(n)，最坏情况下为 O(n^2)，因此如果您担心最坏情况，请使用二分搜索解决方案。

1
我不理解最坏情况。使用哈希表应该在插入和查找时得到O(1)的时间复杂度（需要一些小心），或者你考虑了潜在的哈希冲突吗？无论如何，这似乎比使用二分查找还要好。 - Matthieu M.
4
是的，可能会出现哈希冲突。例如，考虑包含n个1的数组{1, 1, 1, ..., 1, 1, 1, ...}。我们想让它们的和为20。您需要将同一位置上的所有1相加，然后对于每个1，您需要检查数组中是否存在19。假设值19映射到哈希表中与值1相同的位置。这意味着对于每个1，您将在哈希表中执行n次检查，从而导致二次时间复杂度。类似的例子也可以应用于使用3个值（一个占主导地位）有解的情况。 - IVlad
1
你可以将频率映射为每个相关数字的值。因此，如果有8个1，则哈希将映射为1 => 8。例如，当需要求和为2时，您可以添加一个额外的检查 - 如果当前数字等于目标数字（S-数组[i]），则其频率必须至少为2。 - Anurag
10

假设我们想在数组A中找到两个数，它们相加等于N。

  1. 将数组排序。
  2. 找到小于N/2的最大数字，并将该数字的索引设置为lower。
  3. 将upper初始化为lower+1。
  4. 设置sum=A[lower]+ A[upper]。
  5. 如果sum == N，则完成。
  6. 如果sum< N，则增加upper。
  7. 如果sum> N，则减少lower。
  8. 如果任何一个lower或upper超出了数组范围，则没有匹配项。
  9. 返回步骤4。

排序可以在O(n log n)时间内完成。搜索可以在线性时间内完成。

4

这是Java代码: 它甚至删除可能存在的重复值。时间复杂度为O(n^2)

private static int[] intArray = {15,5,10,20,25,30};
private static int sum = 35;

private static void algorithm()
{
    Map<Integer, Integer> intMap = new Hashtable<Integer, Integer>();
    for (int i=0; i<intArray.length; i++) 
    {
        intMap.put(i, intArray[i]);
        if(intMap.containsValue(sum - intArray[i]))
            System.out.println("Found numbers : "+intArray[i] +" and "+(sum - intArray[i]));

    }
    System.out.println(intMap);
}
1
这个解决方案并不是最优的，因为containsValue在线性时间内运行，因此总运行时间为O(n^2)。 - Ivaylo Toskov
2
def sum_in(numbers, sum_):
    """whether any two numbers from `numbers` form `sum_`."""
    a = set(numbers) # O(n)
    return any((sum_ - n) in a for n in a) # O(n)

例子：

>>> sum_in([200, -10, -100], 100)
True
1
注意：此解决方案允许重复，即它不区分 [1] 和 [1, 1] 的情况。 - jfs
1
这里有一个算法，如果数组已经排序，则运行时间为O(n)，否则为O(n log n)。它参考了很多其他答案。代码是用Java编写的，但这里也有一个伪代码，它源自很多现有答案，但通常会针对重复项进行优化。
1. 如果第一个和最后一个元素等于目标，则猜测正确。 2. 创建一个Map，其中包含当前值及其出现次数。 3. 创建一个visited Set，其中包含我们已经看到的项目，这样可以针对重复项进行优化，例如对于输入(1,1,1,1,1,1,2)和目标4，我们只计算0和最后一个元素，而不是数组中的所有1。 4. 使用这些变量来计算目标在数组中的存在性; 将currentValue设置为array[ith]; 将newTarget设置为target - currentValue; 如果currentValue等于newTarget，则将expectedCount设置为2，否则为1 只有当以下条件均满足时，才返回true： a. 我们以前没有看到过这个整数； b. 我们创建的map中有newTarget的某些值； c. newTarget的计数等于或大于expectedCount 5. 否则重复步骤4，直到达到数组末尾并返回false。

正如我所提到的，拜访过的店铺的最佳用途是当我们有重复元素时，如果没有任何元素是重复的，它永远不会有帮助。

Java代码位于https://gist.github.com/eded5dbcee737390acb4

1

这是C语言的一个尝试。这不是标记为作业。

// Assumes a sorted integer array with no duplicates
void printMatching(int array[], int size, int sum)
{
   int i = 0, k = size - 1;
   int curSum;
   while(i < k)
   {
      curSum = array[i] + array[k];
      if(curSum == sum)
      {
         printf("Found match at indices %d, %d\n", i, k);
         i++;k--;
      }
      else if(curSum < sum)
      {
         i++;
      }
      else
      {
         k--;
      }
   }
}

以下是一些测试输出，使用int a[] = { 3, 5, 6, 7, 8, 9, 13, 15, 17 };

Searching for 12..
Found match at indices 0, 5
Found match at indices 1, 3
Searching for 22...
Found match at indices 1, 8
Found match at indices 3, 7
Found match at indices 5, 6
Searching for 4..
Searching for 50..

搜索是线性的，因此为O(n)。如果使用其中一种好的排序算法，则在幕后进行的排序将为O(n*logn)。

由于大O背后的数学原理，加法项中的较小项将有效地从计算中消失，最终得到的结果为O(n logn)。

1

这个是O(n)的。

public static bool doesTargetExistsInList(int Target, int[] inputArray)
{
    if (inputArray != null && inputArray.Length > 0 )
    {
        Hashtable inputHashTable = new Hashtable();

        // This hash table will have all the items in the input array and how many times they appeard
        Hashtable duplicateItems = new Hashtable();

        foreach (int i in inputArray)
        {
            if (!inputHashTable.ContainsKey(i))
            {
                inputHashTable.Add(i, Target - i);
                duplicateItems.Add(i, 1);
            }
            else
            {
                duplicateItems[i] = (int)duplicateItems[i] + 1;    
            }

        }

        foreach (DictionaryEntry de in inputHashTable)
        {
            if ((int)de.Key == (int)de.Value)
            {
                if ((int)duplicateItems[de.Key] > 1)
                return true;
            }
            else if (inputHashTable.ContainsKey(de.Value))
            {
                return true;
            }
        }
    }
    return false;
}
1
这个程序使用了两次遍历。但是它可以只用一次遍历完成，对吧？ - dchang
0
  1. 使用Swift 4.0解决了这个问题
  2. 用3种不同的方法解决了问题（其中包括2种不同类型的返回值——布尔值和索引）

A）时间复杂度 => 0(n Log n) 空间复杂度 => 0(n)。

B）时间复杂度 => 0(n^2) 空间复杂度 => 0(1)。

C）时间复杂度 => 0(n) 空间复杂度 => 0(n)

  • 根据权衡选择方案A、B或C。

    //***********************方案A*********************//
//如果数组中存在任意两对符合条件的元素，则此方案返回TRUE
func binarySearch(list: [Int], key: Int, start: Int, end: Int) -> Int? { //辅助函数

            if end < start {
                return -1
            } else {
                let midIndex = (start + end) / 2

                if list[midIndex] > key {
                    return binarySearch(list: list, key: key, start: start, end:  midIndex - 1)
                } else if list[midIndex] < key {
                    return binarySearch(list: list, key: key, start: midIndex + 1, end: end)
                } else {
                    return midIndex
                }
            }
        }

        func twoPairSum(sum : Int, inputArray: [Int]) -> Bool {

            //仅当数组未排序时执行以下操作！
            let sortedArray = inputArray.sorted()

            for (currentIndex, value)  in sortedArray.enumerated() {
                if let indexReturned =  binarySearch(list: sortedArray, key: sum - value, start: 0, end: sortedArray.count-1) {
                    if indexReturned != -1 && (indexReturned != currentIndex) {
                        return true
                    }
                }
            }
            return false
        }

 //***********************方案B*********************//
 //如果数组中存在任意两对符合条件的元素，则此方案返回这两对元素的索引
 func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] {

            for currentIndex in 0..<nums.count {
                for nextIndex in currentIndex+1..<nums.count {
                    if calculateSum(firstElement: nums[currentIndex], secondElement: nums[nextIndex], target: target) {
                        return [currentIndex, nextIndex]
                    }
                }
            }

            return []
        }

        func calculateSum (firstElement: Int, secondElement: Int, target: Int) -> Bool {//辅助函数
            return (firstElement + secondElement) == target
        }

    //*******************方案C*********************//
   //如果数组中存在任意两对符合条件的元素，则此方案返回这两对元素的索引
   func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] {

            var dict = [Int: Int]()

            for (index, value) in nums.enumerated() {
                dict[value] = index
            }

            for (index, value) in nums.enumerated() {
                let otherIndex = dict[(target - value)]
                if otherIndex != nil && otherIndex != index {
                    return [index, otherIndex!]
                }
            }

            return []
        }
    • 网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接