以下程序的高效解决方案和最佳数据结构

Question

我正在寻找解决这个问题的有效方法，即...编写一个程序来查找总和等于给定数字的所有整数对。例如，如果输入整数数组是{2, 6, 3, 9, 11}并且给定总和是9，则输出应该是{6,3}

现在我尝试的是以下内容，但我知道这不是一个可行且有效的解决方案。。

从数组中取一个数字，然后循环遍历数组和输出对，这等于给定的总和。您对第一个数组中的所有数字都这样做，

import java.util.Arrays;

/**
 * Java Program to find pairs on integer array whose sum is equal to k

 */
public class ProblemInArray{

    public static void main(String args[]) {
        int[] numbers = { 2, 4, 3, 5, 7, 8, 9 };
        int[] numbersWithDuplicates = { 2, 4, 3, 5, 6, -2, 4, 7, 8, 9 };
        prettyPrint(numbers, 7);
        prettyPrint(numbersWithDuplicates, 7);
    }

    /**
     * Prints all pair of integer values from given array whose sum is is equal to given number.
     * complexity of this solution is O(n^2)
     */
    public static void printPairs(int[] array, int sum) {

        for (int i = 0; i < array.length; i++) {
            int first = array[i];
            for (int j = i + 1; j < array.length; j++) {
                int second = array[j];

                if ((first + second) == sum) {
                    System.out.printf("(%d, %d) %n", first, second);
                }
            }

        }
    }
    /**
     * Utility method to print input and output for better explanation.
     */
    public static void prettyPrint(int[] givenArray, int givenSum){
        System.out.println("Given array : " + Arrays.toString(givenArray));
        System.out.println("Given sum : " + givenSum);
        System.out.println("Integer numbers, whose sum is equal to value : " + givenSum);
        printPairs(givenArray, givenSum);
    }

}

Output:
Given sum : 7
Integer numbers, whose sum is equal to value : 7
(2, 5) 
(4, 3) 
Given array : [2, 4, 3, 5, 6, -2, 4, 7, 8, 9]
Given sum : 7
Integer numbers, whose sum is equal to value : 7
(2, 5) 
(4, 3) 
(3, 4) 
(-2, 9) 

Answer 1

这是我的代码：

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class FindPairs {
    public static void main(String args[]) {
        Integer[] numbers = { 2, 4, 3, 5, 7, 8, 9 };
        int sum = 7;
        List<Integer> Numbers = Arrays.asList(numbers);
        Collections.sort(Numbers);
        for (int i : Numbers) {
            if (Numbers.contains(sum - i) && i <= (sum / 2) && i != (sum - i)) {
                System.out.print((sum - i) + " & ");
                System.out.println(+i);
            }
        }
    }
}

条件i

答复：

5.

4.

Answer 2

您可以使用HashMap。如果所需的总和-当前项达到现有值，则可以确保这是一个可能的匹配项。否则，添加当前项目并继续。这应该在O（n）中运行。

public static final void sums(final int sum, final int[] numbers){
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    for(int i : numbers){
        if(map.containsKey(sum-i)){
             System.out.println("( "+map.get(sum-i) +" "+ i+" )");
        }else{
            map.put(i,i);
        }
    }
}