我们需要在数组中找到一对数，其总和等于给定值 .

A = {6,4,5,7,9,1,2}

Sum = 10然后对是 - {6,4}，{9,1}

我有两个解决方案 .

一个O（nlogn）解决方案 - 用2个迭代器（开始和结束）排序校验和 .
一个O（n）解决方案 - 散列数组 . 然后检查哈希表中是否存在 sum-hash[i] .

但是，问题在于虽然第二种解决方案是O（n）时间，但也使用O（n）空间 .

所以，我想知道我们是否可以在 O(n) 时间和 O(1) 空间内完成 . 这不是功课！

18 回答

如果数组中的两个整数与比较整数匹配，则以下代码返回true .

function compareArraySums(array, compare){

        var candidates = [];

        function compareAdditions(element, index, array){
            if(element <= y){
                candidates.push(element);
            }
        }

        array.forEach(compareAdditions);

        for(var i = 0; i < candidates.length; i++){
            for(var j = 0; j < candidates.length; j++){
                if (i + j === y){
                    return true;
                }
            }
        }
    }

回复于 2024-05-01T10:26:36+08:00

下面的代码采用数组和数字N作为目标总和 . 首先对数组进行排序，然后获取包含剩余元素的新数组，然后不通过二进制搜索扫描，而是同时扫描剩余部分和数组 .

public static int solution(int[] a, int N) {

    quickSort(a, 0, a.length-1);    // nlog(n)

    int[] remainders = new int[a.length];

    for (int i=0; i<a.length; i++) {
        remainders[a.length-1-i] = N - a[i];     // n
    }

    int previous = 0;

    for (int j=0; j<a.length; j++) {            // ~~ n

        int k = previous;

        while(k < remainders.length && remainders[k] < a[j]) {
            k++;
        }

        if(k < remainders.length && remainders[k] == a[j]) {
            return 1;
        }

        previous = k;
    }

    return 0;
}

回复于 2024-05-01T10:26:36+08:00

不应该从两端迭代才能解决问题？

对数组进行排序 . 并从两端开始比较 .

if((arr[start] + arr[end]) < sum) start++;
if((arr[start] + arr[end]) > sum) end--;
if((arr[start] + arr[end]) = sum) {print arr[start] "," arr[end] ; start++}
if(start > end)  break;

时间复杂度 O(nlogn)

回复于 2024-05-01T10:26:36+08:00

0
如果它是一个 sorted 数组并且我们只需要一对数字而不是所有对，我们就可以这样做：
```
public void sums(int a[] , int x){ // A = 1,2,3,9,11,20 x=11
    int i=0 , j=a.length-1;
    while(i < j){
      if(a[i] + a[j] == x) system.out.println("the numbers : "a[x] + " " + a[y]);
      else if(a[i] + a[j] < x) i++;
      else j--;
    }
}
```
1 2 3 9 11 20 || i = 0，j = 5 sum = 21 x = 11
1 2 3 9 11 20 || i = 0，j = 4 sum = 13 x = 11
1 2 3 9 11 20 || i = 0，j = 4 sum = 11 x = 11
结束
回复于 2024-05-01T10:26:36+08:00
18

使用就地基数排序和OP的第一个解决方案与2个迭代器相互接近 .

如果数组中的数字不是某种多精度数字并且例如是32位整数，则可以使用几乎没有额外空间（每次传递1位）在2 * 32次传递中对它们进行排序 . 或者2 * 8遍和16个整数计数器（每遍4位） .

Details for the 2 iterators solution:

第一个迭代器最初指向排序数组的第一个元素并向前推进 . 第二个迭代器最初指向数组的最后一个元素并向后前进 .

如果迭代器引用的元素总和小于所需的值，则前进第一个迭代器 . 如果它大于所需的值，则前进第二个迭代器 . 如果它等于所需的值，则成功 .

只需要一次传递，因此时间复杂度为O（n） . 空间复杂度为O（1） . 如果使用基数排序，整个算法的复杂性是相同的 .

如果您对相关问题感兴趣（总和超过2个数字），请参阅"Sum-subset with a fixed subset size"和"Finding three elements in an array whose sum is closest to an given number" .

回复于 2024-05-01T10:26:36+08:00
1
这是来自微软亚洲研究院的经典访谈问题 .
如何在未排序的数组中查找等于给定总和的2个数字 .

[1]蛮力解决方案
这个算法很简单 . 时间复杂度为O（N ^ 2）

[2]使用二进制搜索
使用bianry搜索找到每个arr [i]的Sum-arr [i]，时间复杂度可以减少到O（N * logN）

[3]使用哈希
基于[2]算法并使用哈希，时间复杂度可以减少到O（N），但是这个解决方案将添加哈希的O（N）空间 .

[4]最优算法：

Pseduo代码：
```
for(i=0;j=n-1;i<j)
   if(arr[i]+arr[j]==sum) return (i,j);
else if(arr[i]+arr[j]<sum) i++;
else j--;
return(-1,-1);
```
要么
```
If a[M] + a[m] > I then M--
If a[M] + a[m] < I then m++
If a[M] + a[m] == I you have found it
If m > M, no such numbers exist.
```
而且，这个问题完全解决了吗？否 . 如果数字是N.这个问题将变得非常复杂 .

问题然后：
如何找到具有给定数字的所有组合案例？

这是一个经典的NP-Complete问题，称为subset-sum .
要了解NP / NPC / NP-Hard，您最好阅读一些专业书籍 .

参考文献：
[1] http://www.quora.com/Mathematics/How-can-I-find-all-the-combination-cases-with-a-given-number
[2] http://en.wikipedia.org/wiki/Subset_sum_problem
回复于 2024-05-01T10:26:36+08:00

for (int i=0; i < array.size(); i++){
  int value = array[i];
  int diff = sum - value; 
  if (! hashSet.contains(diffvalue)){
      hashSet.put(value,value);
  } else{
       printf(sum = diffvalue + hashSet.get(diffvalue));
  } 
}

--------
Sum being sum of 2 numbers.

回复于 2024-05-01T10:26:36+08:00

0
如果您假设对假设求和的值 M 是常量并且数组中的条目是正数，那么您可以使用 M/2 指针（ O(1) 空格）在一次传递（ O(n) 时间）中执行此操作，如下所示 . 指针标记为 P1,P2,...,Pk ，其中 k=floor(M/2) . 然后做这样的事情
```
for (int i=0; i<N; ++i) {
  int j = array[i];
  if (j < M/2) {
    if (Pj == 0)
      Pj = -(i+1);   // found smaller unpaired
    else if (Pj > 0)
      print(Pj-1,i); // found a pair
      Pj = 0;
  } else
    if (Pj == 0)
      Pj = (i+1);    // found larger unpaired
    else if (Pj < 0)
      print(Pj-1,i); // found a pair
      Pj = 0;
  }
}
```
例如，您可以通过将索引存储为base N 中的数字来处理重复的条目（例如，两个6） . 对于 M/2 ，您可以添加条件
```
if (j == M/2) {
    if (Pj == 0)
      Pj = i+1;      // found unpaired middle
    else
      print(Pj-1,i); // found a pair
      Pj = 0;
  }
```
但是现在你有把这些配对放在一起的问题 .
回复于 2024-05-01T10:26:36+08:00

public void printPairsOfNumbers(int[] a, int sum){
    //O(n2)
    for (int i = 0; i < a.length; i++) {
        for (int j = i+1; j < a.length; j++) {
            if(sum - a[i] == a[j]){
                //match..
                System.out.println(a[i]+","+a[j]);
            }
        }
    }

    //O(n) time and O(n) space
    Set<Integer> cache = new HashSet<Integer>();
    cache.add(a[0]);
    for (int i = 1; i < a.length; i++) {
        if(cache.contains(sum - a[i])){
            //match//
            System.out.println(a[i]+","+(sum-a[i]));
        }else{
            cache.add(a[i]);
        }
    }

}

回复于 2024-05-01T10:26:36+08:00

3

明显的解决方案不起作用（迭代每个连续的对）或者是任何顺序的两个数字吗？

在这种情况下，您可以对数字列表进行排序，并使用随机抽样对已排序的列表进行分区，直到您有一个足够小的子列表进行迭代 .

回复于 2024-05-01T10:26:36+08:00

public static ArrayList<Integer> find(int[] A , int target){
    HashSet<Integer> set = new HashSet<Integer>();
    ArrayList<Integer> list = new ArrayList<Integer>();
    int diffrence = 0;
    for(Integer i : A){
        set.add(i);
    }
    for(int i = 0; i <A.length; i++){
        diffrence = target- A[i];
    if(set.contains(diffrence)&&A[i]!=diffrence){
        list.add(A[i]);
        list.add(diffrence);
        return list;
    }
     }
    return null;
}

回复于 2024-05-01T10:26:36+08:00

`package algorithmsDesignAnalysis;

 public class USELESStemp {
 public static void main(String[] args){
    int A[] = {6, 8, 7, 5, 3, 11, 10}; 

    int sum = 12;
    int[] B = new int[A.length];
    int Max =A.length; 

    for(int i=0; i<A.length; i++){
        B[i] = sum - A[i];
        if(B[i] > Max)
            Max = B[i];
        if(A[i] > Max)
            Max = A[i];

        System.out.print(" " + B[i] + "");

    } // O(n) here; 

    System.out.println("\n Max = " + Max);

    int[] Array = new int[Max+1];
    for(int i=0; i<B.length; i++){
        Array[B[i]] = B[i];
    } // O(n) here;

    for(int i=0; i<A.length; i++){  
    if (Array[A[i]] >= 0)
        System.out.println("We got one: " + A[i] +" and " + (sum-A[i]));
    } // O(n) here;

} // end main();

/******
Running time: 3*O(n)
*******/
}

回复于 2024-05-01T10:26:36+08:00

Python 2.7实现：

import itertools
list = [1, 1, 2, 3, 4, 5,]
uniquelist = set(list)
targetsum = 5
for n in itertools.combinations(uniquelist, 2):
    if n[0] + n[1] == targetsum:
    print str(n[0]) + " + " + str(n[1])

输出：

1 + 4
2 + 3

回复于 2024-05-01T10:26:36+08:00

https://github.com/clockzhong/findSumPairNumber

#! /usr/bin/env python
import sys
import os
import re


#get the number list
numberListStr=raw_input("Please input your number list (seperated by spaces)...\n")
numberList=[int(i) for i in numberListStr.split()]
print 'you have input the following number list:'
print numberList

#get the sum target value
sumTargetStr=raw_input("Please input your target number:\n")
sumTarget=int(sumTargetStr)
print 'your target is: '
print sumTarget


def generatePairsWith2IndexLists(list1, list2):
    result=[]
    for item1 in list1:
        for item2 in list2:
            #result.append([item1, item2])
            result.append([item1+1, item2+1])
    #print result
    return result

def generatePairsWithOneIndexLists(list1):
    result=[]
    index = 0
    while index< (len(list1)-1):
        index2=index+1
        while index2 < len(list1):
            #result.append([list1[index],list1[index2]])
            result.append([list1[index]+1,list1[index2]+1])
            index2+=1
        index+=1
    return result


def getPairs(numList, target):
    pairList=[]
    candidateSlots=[] ##we have (target-1) slots 

    #init the candidateSlots list
    index=0
    while index < target+1:
        candidateSlots.append(None)
        index+=1

    #generate the candidateSlots, contribute O(n) complexity
    index=0
    while index<len(numList):
        if numList[index]<=target and numList[index]>=0:
            #print 'index:',index
            #print 'numList[index]:',numList[index]     
            #print 'len(candidateSlots):',len(candidateSlots)
            if candidateSlots[numList[index]]==None:
                candidateSlots[numList[index]]=[index]
            else:
                candidateSlots[numList[index]].append(index)
        index+=1

    #print candidateSlots

    #generate the pairs list based on the candidateSlots[] we just created
    #contribute O(target) complexity
    index=0
    while index<=(target/2):
        if candidateSlots[index]!=None and candidateSlots[target-index]!=None:
            if index!=(target-index):
                newPairList=generatePairsWith2IndexLists(candidateSlots[index], candidateSlots[target-index])
            else:
                newPairList=generatePairsWithOneIndexLists(candidateSlots[index])
            pairList+=newPairList
        index+=1

    return pairList

print getPairs(numberList, sumTarget)

我已经成功地在O（n m）时间和空间成本下使用Python实现了一个解决方案 . “m”表示这两个数和的总和所需的目标值 . 我相信这是最低的成本 . Erict2k使用了itertools.combinations，与我的算法相比，它也会花费相似或更高的时间和空间成本 .

回复于 2024-05-01T10:26:36+08:00

0

如果数字不是很大，你可以使用快速傅立叶变换乘以两个多项式，然后在O（1）中检查x ^（所需总和）和之前的系数是否大于零 . O（n log n）总计！

回复于 2024-05-01T10:26:36+08:00

//使用Hashing导入java.io. *的Java实现;

class PairSum {private static final int MAX = 100000; // Hashmap的最大大小

static void printpairs(int arr[],int sum)
{
    // Declares and initializes the whole array as false
    boolean[] binmap = new boolean[MAX];

    for (int i=0; i<arr.length; ++i)
    {
        int temp = sum-arr[i];

        // checking for condition
        if (temp>=0 && binmap[temp])
        {
            System.out.println("Pair with given sum " +
                                sum + " is (" + arr[i] +
                                ", "+temp+")");
        }
        binmap[arr[i]] = true;
    }
}

// Main to test the above function
public static void main (String[] args)
{
    int A[] = {1, 4, 45, 6, 10, 8};
    int n = 16;
    printpairs(A,  n);
}

}

回复于 2024-05-01T10:26:36+08:00

-1

使用对键（列表中的数字）创建字典，值是获取所需值所需的数字 . 接下来，检查列表中是否存在数字对 .

def check_sum_in_list(p_list, p_check_sum):
    l_dict = {i: (p_check_sum - i) for i in p_list}
    for key, value in l_dict.items():
        if key in p_list and value in p_list:
            return True
    return False


if __name__ == '__main__':
    l1 = [1, 3, 7, 12, 72, 2, 8]
    l2 = [1, 2, 2, 4, 7, 4, 13, 32]

    print(check_sum_in_list(l1, 10))
    print(check_sum_in_list(l2, 99))

Output:
True
Flase

版本2

import random


def check_sum_in_list(p_list, p_searched_sum):
    print(list(p_list))
    l_dict = {i: p_searched_sum - i for i in set(p_list)}
    for key, value in l_dict.items():
        if key in p_list and value in p_list:
            if p_list.index(key) != p_list.index(value):
                print(key, value)
                return True
    return False


if __name__ == '__main__':
    l1 = []
    for i in range(1, 2000000):
        l1.append(random.randrange(1, 1000))

    j = 0
    i = 9
    while i < len(l1):
        if check_sum_in_list(l1[j:i], 100):
            print('Found')
            break
        else:
            print('Continue searching')
            j = i
            i = i + 10

Output:
...
[154, 596, 758, 924, 797, 379, 731, 278, 992, 167]
Continue searching
[808, 730, 216, 15, 261, 149, 65, 386, 670, 770]
Continue searching
[961, 632, 39, 888, 61, 18, 166, 167, 474, 108]
39 61
Finded
[Finished in 3.9s]

回复于 2024-05-01T10:26:36+08:00

public static void Main(string[] args)
    {
        int[] myArray =  {1,2,3,4,5,6,1,4,2,2,7 };
        int Sum = 9;

            for (int j = 1; j < myArray.Length; j++)
            {                    
                if (myArray[j-1]+myArray[j]==Sum)
                {
                    Console.WriteLine("{0}, {1}",myArray[j-1],myArray[j]);
                }
            }            
        Console.ReadLine();
    }

回复于 2024-05-01T10:26:36+08:00

在未排序的数组中找到等于给定总和的2个数字

18 回答

Python 2.7实现：

输出：

相关问题