在java 中的Array 中找到总和最接近X 的对。

Question

给定一个已排序的数组，我们需要在 Array 中找到一个总和接近于数字 X 的对。
例如：

array[]={-40,-5,1,3,6,7,8,20};
The pair whose sum is closest to 5 :  1 and 3

Answer 1

解决方案1：
您可以检查每对数字并找到接近 X 的总和。
Java 代码：

public static void findPairWithClosestToXBruteForce(int arr[],int X)
{
    if(arr.length<2)
        return;
    // Suppose 1st two element has minimum diff with X
    int minimumDiff=Math.abs(arr[0]+arr[1]-X);
    int pair1stIndex=0;
    int pair2ndIndex=1;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i+1; j < arr.length; j++) {
            int tempDiff=Math.abs(arr[i]+arr[j]-X);

            if(tempDiff< minimumDiff)
            {
                pair1stIndex=i;
                pair2ndIndex=j;
                minimumDiff=tempDiff;
            }
        }
    }
    System.out.println(" The pair whose sum is closest to X using brute force method: "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]);
}

解决方案2：
我们将维护两个索引，一个在开头（l=0），一个在结尾（r=n-1） * 迭代直到 l < r * 将差异计算为 arr[l] + arr[r]-x * 如果 abs (diff) < minDiff 然后更新最小总和和对。 * 如果 arr[l] + arr[r] 小于 X，这意味着如果我们想找到接近 X 的和，做 r– * 如果 arr[l] + arr[r] 大于 0，这意味着如果我们想找到接近 X 的总和，请执行 l++
java代码：

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

    int minimumDiff = Integer.MAX_VALUE;
    int n=arr.length;
    if(n<0)
        return;
    // left and right index variables
    int l = 0, r = n-1;

    // variable to keep track of the left and right pair for minimumSum
    int minLeft = l, minRight = n-1;

    while(l < r)
    {

        int currentDiff= Math.abs(arr[l] + arr[r]-X);
        /*If abs(diff) is less than min dif, we need to update sum and pair */
        if(currentDiff < minimumDiff)
        {
            minimumDiff = currentDiff;
            minLeft = l;
            minRight = r;
        }
        if(arr[l] + arr[r] < X)
            l++;
        else
            r--;
    }

    System.out.println(" The pair whose sum is closest to X : "+arr[minLeft]+" "+ arr[minRight]);
}

时间复杂度：O(NLogN)

寻找总和最接近 X 的对的 Java 程序：

package org.arpit.java2blog;

public class FindPairClosestToXMain {

    public static void main(String[] args)
    {
        int array[]={-40,-5,1,3,6,7,8,20};
        findPairWithClosestToXBruteForce(array,5);
        findPairWithClosestToX(array,5);
    }
    public static void  findPairWithClosestToXBruteForce(int arr[],int X)
    {
        if(arr.length<2)
            return;
        // Suppose 1st two element has minimum diff with X
        int minimumDiff=Math.abs(arr[0]+arr[1]-X);
        int pair1stIndex=0;
        int pair2ndIndex=1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                int tempDiff=Math.abs(arr[i]+arr[j]-X);

                if(tempDiff< minimumDiff)
                {
                    pair1stIndex=i;
                    pair2ndIndex=j;
                    minimumDiff=tempDiff;
                }
            }
        }
        System.out.println(" The pair whose sum is closest to X using brute force method: "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]);
    }

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

        int minimumDiff = Integer.MAX_VALUE;
        int n=arr.length;
        if(n<0)
            return;
        // left and right index variables
        int l = 0, r = n-1;

        // variable to keep track of the left and right pair for minimumSum
        int minLeft = l, minRight = n-1;

        while(l < r)
        {

            int currentDiff= Math.abs(arr[l] + arr[r]-X);
            /*If abs(diff) is less than min dif, we need to update sum and pair */
            if(currentDiff < minimumDiff)
            {
                minimumDiff = currentDiff;
                minLeft = l;
                minRight = r;
            }
            if(arr[l] + arr[r] < X)
                l++;
            else
                r--;
        }

        System.out.println(" The pair whose sum is closest to X : "+arr[minLeft]+" "+ arr[minRight]);
    }
}

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

   The pair whose sum is closest to X using brute force method: 1 3
The pair whose sum is closest to X : 1 3