找到添加到给定总和的数组中的数字对

Question

问题:给定一个未排序的正整数数组,是否有可能从该数组中找到一对总和达到给定总和的整数？

约束:这应该在O(n)和就地(没有任何外部存储,如数组,哈希映射)完成(你可以使用额外的变量/指针)

如果这是不可能的,那么可以给出相同的证明吗？

Answer 1

如果你有一个排序数组,你可以通过向中间移动两个指针在O(n)中找到这样一对

i = 0
j = n-1
while(i < j){
   if      (a[i] + a[j] == target) return (i, j);
   else if (a[i] + a[j] <  target) i += 1;
   else if (a[i] + a[j] >  target) j -= 1;
}
return NOT_FOUND;

如果您对数字的大小有界限(或者如果数组已经排在第一位),则可以对O(N)进行排序.即使这样,log n因子也很小,我不想费心去掉它.

证明:

如果有一个解决方案(i*, j*),假设,不失一般性,即i到达i*之前j到达j*.由于所有j'之间j*和j我们知道a[j'] > a[j*]我们可以推断出a[i] + a[j'] > a[i*] + a[j*] = target,因此,所有的算法以下步骤将导致J可降低,直到达到j*(或同等价值)不给i机会向前前进和"小姐"的解.

另一个方向的解释是类似的.

Answer 2

适用于排序数组的O(N)时间和O(1)空间解决方案:

让M你成为你追求的价值.使用两个指针,X和Y.开始X=0在开始和Y=N-1结尾.计算总和sum = array[X] + array[Y].如果sum > M,则递减Y,否则递增X.如果指针交叉,则不存在解决方案.

您可以对一般阵列进行排序,但我不确定是否存在O(N)时间和O(1)空间解决方案.

Answer 3

我的 Java 解决方案（时间复杂度 O(n)），这将输出具有给定总和的所有对

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

public class Test {
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Map<Integer, Integer> hash = new HashMap<>();
    int arr[] = {1,4,2,6,3,8,2,9};
    int sum = 5;
    for (int i = 0; i < arr.length; i++) {
        hash.put(arr[i],i);
    }
    
    for (int i = 0; i < arr.length; i++) {
        if(hash.containsKey(sum-arr[i])){
            //System.out.println(i+ " " +  hash.get(sum-arr[i]));
             System.out.println(arr[i]+ " " + (sum-arr[i]));
        }
    }
}
}