从一个数组中找出总和等于给定数字的所有元素对

Question

给定一个数组，我们需要找到总和等于数字 X 的所有对。
例如：

array[]={ -40, -5, 1, 3, 6, 7, 8, 20 };
Pair of elements whose sum is equal to 15 :  7, 8 and -5, 20

Answer 1

解决方案1：
您可以检查每一对数字，并找到总和等于 X。
Java 代码：

public static void findPairsWithSumEqualsToXBruteForce(int arr[], int X) {
    if (arr.length < 2)
        return;

    System.out.println("The pair whose sum is equal to 15 using brute force method: ");
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            int tempSum = arr[i] + arr[j];

            if (tempSum == X) {
                System.out.println(arr[i] + " " + arr[j]);
            }
        }
    }
}

解决方案2：
对数组进行排序 * 我们将维护两个索引，一个在开头（l=0），一个在结尾（r=n-1） * 迭代直到 l < r * 检查 arr[l] + arr[r] 是否等于 X * 如果是，则打印该对并执行 l , r– * 如果 arr[l] + arr[r] 小于 X，这意味着如果我们想找到接近 X 的和，做 r– * 如果 arr[l] + arr[r] 大于 X，这意味着如果我们想找到接近 X 的总和，请执行 l

java代码：

public static void findPairsEqualsToX(int arr[], int X) {

    int n = arr.length;
    if (n < 2)
        return;
    Arrays.sort(arr);
    System.out.println("The pair whose sum is equal to 15 : ");
    // left and right index variables
    int l = 0, r = n - 1;

    while (l < r) {
        int currentSum = arr[l] + arr[r];
        if (currentSum == X) {
            System.out.println(arr[l] + " " + arr[r]);
            l++;
            r--;
        } else if (arr[l] + arr[r] < X)
            l++;
        else
            r--;
    }
}

时间复杂度：O(NLogN)

解决方案3：
使用哈希

• 将数组元素放入HashMap，元素为键，索引为值。
• 遍历数组 arr[]
• 检查 arr[i]，如果 X-arr[i] 存在于 HashMap 中。
• 如果是，我们已经找到了这对并打印出来。
  java代码：

public static void findPairsEqualsToXUsingHashing(int arr[], int X) {
    HashMap<Integer, Integer> elementIndexMap = new HashMap<Integer, Integer>();
    System.out.println("The pair whose sum is equal to 15 : ");
    for (int i = 0; i < arr.length; i++) {
        elementIndexMap.put(arr[i], i);
    }
    for (int i = 0; i < arr.length; i++) {
        // we have used elementIndexMap.get(X-arr[i])!=i to avoid using same
        // element twice
        if (elementIndexMap.get(X - arr[i]) != null && elementIndexMap.get(X - arr[i]) != i) //
        {
            System.out.println(arr[i] + " " + (X - arr[i]));
        }
    }
}

时间复杂度：O(NLogN) 空间复杂度：O(N)
查找总和等于给定数字的所有对的 Java 程序：

package org.arpit.java2blog;

import java.util.Arrays;
import java.util.HashMap;

public class FindPairEqualToGivenNumberMain {

    public static void main(String[] args) {
        int array[] = { -40, -5, 1, 3, 6, 7, 8, 20 };
        findPairsWithSumEqualsToXBruteForce(array, 15);
        findPairsEqualsToX(array, 15);
        findPairsEqualsToXUsingHashing(array, 15);
    }

    public static void findPairsWithSumEqualsToXBruteForce(int arr[], int X) {
        if (arr.length < 2)
            return;

        System.out.println("The pair whose sum is closest to 15 using brute force method: ");
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int tempSum = arr[i] + arr[j];

                if (tempSum == X) {
                    System.out.println(arr[i] + " " + arr[j]);
                }
            }
        }
    }

    public static void findPairsEqualsToX(int arr[], int X) {

        int n = arr.length;
        if (n < 2)
            return;
        Arrays.sort(arr);
        System.out.println("The pair whose sum is closest to 15 : ");
        // left and right index variables
        int l = 0, r = n - 1;

        while (l < r) {
            int currentSum = arr[l] + arr[r];
            if (currentSum == X) {
                System.out.println(arr[l] + " " + arr[r]);
                l++;
                r--;
            } else if (arr[l] + arr[r] < X)
                l++;
            else
                r--;
        }
    }

    public static void findPairsEqualsToXUsingHashing(int arr[], int X) {
        HashMap<Integer, Integer> elementIndexMap = new HashMap<Integer, Integer>();
        System.out.println("The pair whose sum is closest to 15 : ");
        for (int i = 0; i < arr.length; i++) {
            elementIndexMap.put(arr[i], i);
        }
        for (int i = 0; i < arr.length; i++) {
            // we have used elementIndexMap.get(X-arr[i])!=i to avoid using same
            // element twice
            if (elementIndexMap.get(X - arr[i]) != null && elementIndexMap.get(X - arr[i]) != i) //
            {
                System.out.println(arr[i] + " " + (X - arr[i]));
            }
        }
    }
}

当你运行上面的程序时，你会得到以下输出：

  The pair whose sum is closest to 15 using brute force method: 
-5 20
7 8
The pair whose sum is closest to 15 : 
-5 20
7 8
The pair whose sum is closest to 15 : 
-5 20
7 8
8 7
20 -5