在数组中找到总和最接近零的一对

Question

问题 ：
给定 +ve 和 -ve 整数数组，我们需要在数组中找到总和接近零的一对。
例如：

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

Answer 1

您可以检查每一对数字并找到最小和。
java代码：

public static void findPairWithMinSumBruteForce(int arr[])
{
    if(arr.length<2)
        return;
    // Suppose 1st two element has minimum sum
    int minimumSum=arr[0]+arr[1];
    int pair1stIndex=0;
    int pair2ndIndex=1;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i+1; j < arr.length; j++) {
            int tempSum=arr[i]+arr[j];
            if(Math.abs(tempSum) < Math.abs(minimumSum))
            {
                pair1stIndex=i;
                pair2ndIndex=j;
                minimumSum=tempSum;
            }
        }
    }
    System.out.println(" The pair whose sum is closest to zero : "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]);
}

解决方案2：
对数组进行排序。 * 我们将维护两个索引，一个在开头（l=0），一个在结尾（r=n-1）
迭代直到 l < r * 计算 arr[l] + arr[r] 的总和 * 如果 abs (sum) < abs (minSum)，则更新最小和和对。 * 如果 sum 小于 0，这意味着如果我们想找到接近 0 的 sum，请执行 r– * 如果 sum 大于 0，这意味着如果我们想找到接近 0 的 sum ，请执行 l++

java代码：

public static void findPairWithMinSum(int arr[]) {

        // Sort the array, you can use any sorting algorithm to sort it
        Arrays.sort(arr);
        int sum=0; 
        int minimumSum = Integer.MAX_VALUE;
        int n=arr.length;
        if(n<0)
            return;
        // left and right index variables
        int l = 0, r = n-1;

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

        while(l < r)
        {
            sum = arr[l] + arr[r];

            /*If abs(sum) is less than min sum, we need to update sum and pair */
            if(Math.abs(sum) < Math.abs(minimumSum))
            {
                minimumSum = sum;
                minLeft = l;
                minRight = r;
            }
            if(sum < 0)
                l++;
            else
                r--;
        }

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

时间复杂度：O(NLogN)

查找总和最接近零的对的 Java 程序：

package org.arpit.java2blog;

import java.util.Arrays;

public class findPairClosestToZero {

    public static void main(String[] args)
    {
        int array[]={1,30,-5,70,-8,20,-40,60};
        findPairWithMinSumBruteForce(array);
        findPairWithMinSum(array);
    }
    public static void  findPairWithMinSumBruteForce(int arr[])
    {
        if(arr.length<2)
            return;
        // Suppose 1st two element has minimum sum
        int minimumSum=arr[0]+arr[1];
        int pair1stIndex=0;
        int pair2ndIndex=1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                int tempSum=arr[i]+arr[j];
                if(Math.abs(tempSum) < Math.abs(minimumSum))
                {
                    pair1stIndex=i;
                    pair2ndIndex=j;
                    minimumSum=tempSum;
                }
            }
        }
        System.out.println(" The pair whose sum is closest to zero using brute force method: "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]);
    }

    public static void findPairWithMinSum(int arr[]) {

        // Sort the array, you can use any sorting algorithm to sort it
        Arrays.sort(arr);
        int sum=0; 
        int minimumSum = Integer.MAX_VALUE;
        int n=arr.length;
        if(n<0)
            return;
        // left and right index variables
        int l = 0, r = n-1;

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

        while(l < r)
        {
            sum = arr[l] + arr[r];

            /*If abs(sum) is less than min sum, we need to update sum and pair */
            if(Math.abs(sum) < Math.abs(minimumSum))
            {
                minimumSum = sum;
                minLeft = l;
                minRight = r;
            }
            if(sum < 0)
                l++;
            else
                r--;
        }

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

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

 The pair whose sum is closest to zero using brute force method: 1 -5
 The pair whose sum is closest to zero : -5 1