兩個元素的和最接近零 · GeeksForGeeks 中文系列教程

# 兩個元素的和最接近零 > 原文： [https://www.geeksforgeeks.org/two-elements-whose-sum-is-closest-to-zero/](https://www.geeksforgeeks.org/two-elements-whose-sum-is-closest-to-zero/) **問題**：給出了一個整數數組，包括+ ve 和-ve。您需要找到兩個元素，使它們的總和最接近零。對于以下數組，程序應打印-80 和 85。 **方法 1（簡單）** 對于每個元素，找到它與數組中每個其他元素的總和，并比較總和。最后，返回最小值。 **實現**： ## C++ ```cpp # include <bits/stdc++.h> # include <stdlib.h> /* for abs() */ # include <math.h> using namespace std; void minAbsSumPair(int arr[], int arr_size) { ????int inv_count = 0; ????int l, r, min_sum, sum, min_l, min_r; ????/* Array should have at least ???????two elements*/ ????if(arr_size < 2) ????{ ????????cout << "Invalid Input"; ????????return; ????} ????/* Initialization of values */ ????min_l = 0; ????min_r = 1; ????min_sum = arr[0] + arr[1]; ????for(l = 0; l < arr_size - 1; l++) ????{ ????????for(r = l + 1; r < arr_size; r++) ????????{ ????????sum = arr[l] + arr[r]; ????????if(abs(min_sum) > abs(sum)) ????????{ ????????????min_sum = sum; ????????????min_l = l; ????????????min_r = r; ????????} ????????} ????} ????cout << "The two elements whose sum is minimum are " ?????????<< arr[min_l] << " and " << arr[min_r]; } // Driver Code int main() { ????int arr[] = {1, 60, -10, 70, -80, 85}; ????minAbsSumPair(arr, 6); ????return 0; } // This code is contributed // by Akanksha Rai(Abby_akku) ``` ## C ``` # include <stdio.h> # include <stdlib.h> /* for abs() */ # include <math.h> void minAbsSumPair(int arr[], int arr_size) { ??int inv_count = 0; ??int l, r, min_sum, sum, min_l, min_r; ??/* Array should have at least two elements*/ ??if(arr_size < 2) ??{ ????printf("Invalid Input"); ????return; ??} ??/* Initialization of values */ ??min_l = 0; ??min_r = 1; ??min_sum = arr[0] + arr[1]; ??for(l = 0; l < arr_size - 1; l++) ??{ ????for(r = l+1; r < arr_size; r++) ????{ ??????sum = arr[l] + arr[r]; ??????if(abs(min_sum) > abs(sum)) ??????{ ????????min_sum = sum; ????????min_l = l; ????????min_r = r; ??????} ????} ??} ??printf(" The two elements whose sum is minimum are %d and %d", ??????????arr[min_l], arr[min_r]); } /* Driver program to test above function */ int main() { ??int arr[] = {1, 60, -10, 70, -80, 85}; ??minAbsSumPair(arr, 6); ??getchar(); ??return 0; } ``` ## Java ```java import java.util.*; import java.lang.*; class Main { ????static void minAbsSumPair(int arr[], int arr_size) ????{ ??????int inv_count = 0; ??????int l, r, min_sum, sum, min_l, min_r; ??????/* Array should have at least two elements*/ ??????if(arr_size < 2) ??????{ ????????System.out.println("Invalid Input"); ????????return; ??????} ??????/* Initialization of values */ ??????min_l = 0; ??????min_r = 1; ??????min_sum = arr[0] + arr[1]; ??????for(l = 0; l < arr_size - 1; l++) ??????{ ????????for(r = l+1; r < arr_size; r++) ????????{ ??????????sum = arr[l] + arr[r]; ??????????if(Math.abs(min_sum) > Math.abs(sum)) ??????????{ ????????????min_sum = sum; ????????????min_l = l; ????????????min_r = r; ??????????} ????????} ??????} ??????System.out.println(" The two elements whose "+ ??????????????????????????????"sum is minimum are "+ ????????????????????????arr[min_l]+ " and "+arr[min_r]); ????} ????// main function ????public static void main (String[] args)? ????{ ????????int arr[] = {1, 60, -10, 70, -80, 85}; ????????minAbsSumPair(arr, 6); ????} } ``` ## Python3 ```py # Python3 code to find Two elements # whose sum is closest to zero def minAbsSumPair(arr,arr_size): ????inv_count = 0 ????# Array should have at least ????# two elements ????if arr_size < 2: ????????print("Invalid Input") ????????return ????# Initialization of values? ????min_l = 0 ????min_r = 1 ????min_sum = arr[0] + arr[1] ????for l in range (0, arr_size - 1): ????????for r in range (l + 1, arr_size): ????????????sum = arr[l] + arr[r]????????????????? ????????????if abs(min_sum) > abs(sum):????????? ????????????????min_sum = sum ????????????????min_l = l ????????????????min_r = r ????print("The two elements whose sum is minimum are",? ????????????arr[min_l], "and ", arr[min_r]) # Driver program to test above function? arr = [1, 60, -10, 70, -80, 85] minAbsSumPair(arr, 6); # This code is contributed by Smitha Dinesh Semwal ``` ## C# ```cs // C# code to find Two elements // whose sum is closest to zero using System; class GFG { static void minAbsSumPair(int []arr, ????????????????????????int arr_size) ????{ ????int l, r, min_sum, sum, min_l, min_r; ????/* Array should have at least two elements*/ ????if (arr_size < 2) ????{ ????????Console.Write("Invalid Input"); ????????return; ????} ????/* Initialization of values */ ????min_l = 0; ????min_r = 1; ????min_sum = arr[0] + arr[1]; ????for (l = 0; l < arr_size - 1; l++) ????{ ????????for (r = l+1; r < arr_size; r++) ????????{ ????????????sum = arr[l] + arr[r]; ????????????if (Math.Abs(min_sum) > Math.Abs(sum)) ????????????{ ????????????????min_sum = sum; ????????????????min_l = l; ????????????????min_r = r; ????????????} ????????} ????} ????Console.Write(" The two elements whose "+ ????????????????????????"sum is minimum are "+ ????????????????????arr[min_l]+ " and "+arr[min_r]); ????} ????// main function ????public static void Main ()? ????{ ????????int []arr = {1, 60, -10, 70, -80, 85}; ????????minAbsSumPair(arr, 6); ????} } // This code is contributed by Sam007 ``` ## PHP ```php <?php // PHP program to find the Two elements // whose sum is closest to zero function minAbsSumPair($arr, $arr_size) { ????$inv_count = 0; ????/* Array should have at ????least two elements*/ ????if($arr_size < 2) ????{ ????????echo "Invalid Input"; ????????return; ????} ????/* Initialization of values */ ????$min_l = 0; ????$min_r = 1; ????$min_sum = $arr[0] + $arr[1]; ????for($l = 0; $l < $arr_size - 1; $l++) ????{ ????????for($r = $l+1; $r < $arr_size; $r++) ????????{ ????????$sum = $arr[$l] + $arr[$r]; ????????if(abs($min_sum) > abs($sum)) ????????{ ????????????$min_sum = $sum; ????????????$min_l = $l; ????????????$min_r = $r; ????????} ????????} ????} ????echo "The two elements whose sum is minimum are " ????????????.$arr[$min_l]." and ". $arr[$min_r]; } // Driver Code $arr = array(1, 60, -10, 70, -80, 85); minAbsSumPair($arr, 6); // This code is contributed by Sam007 ?> ``` **輸出**： ``` The two elements whose sum is minimum are -80 and 85 ``` **時間復雜度**： O（n ^ 2） **方法 2（使用排序）** 感謝 baskin 建議這種方法。我們建議閱讀[這篇文章](https://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/)，以了解此方法的背景知識。 **算法** 1）對輸入數組的所有元素進行排序。 2）使用兩個索引變量 l 和 r 分別從左端和右端遍歷。將 l 初始化為 0，將 r 初始化為 n-1。 3）sum = a [l] + a [r] 4）如果 sum 為-ve，則 l ++ 5）如果 sum 為+ ve，則 r– 6）跟蹤絕對最低總金額。 7）重復步驟 3、4、5 和 6，同時< r **實現** ## C++ ``` #include <bits/stdc++.h> using namespace std; void quickSort(int *, int, int);? /* Function to print pair of elements ???having minimum sum */ void minAbsSumPair(int arr[], int n)? {? ????// Variables to keep track? ????// of current sum and minimum sum? ????int sum, min_sum = INT_MAX;? ????// left and right index variables? ????int l = 0, r = n-1;? ????// variable to keep track of? ????// the left and right pair for min_sum? ????int min_l = l, min_r = n-1;? ????/* Array should have at least two elements*/ ????if(n < 2)? ????{? ????????cout << "Invalid Input";? ????????return;? ????}? ????/* Sort the elements */ ????quickSort(arr, l, r);? ????while(l < r)? ????{? ????????sum = arr[l] + arr[r];? ????????/*If abs(sum) is less? ??????????then update the result items*/ ????????if(abs(sum) < abs(min_sum))? ????????{? ????????????min_sum = sum;? ????????????min_l = l;? ????????????min_r = r;? ????????}? ????????if(sum < 0)? ????????????l++;? ????????else ????????????r--;? ????}? ????cout << "The two elements whose sum is minimum are "? ?????????<< arr[min_l] << " and " << arr[min_r];? }? // Driver Code int main()? {? ????int arr[] = {1, 60, -10, 70, -80, 85};? ????int n = sizeof(arr) / sizeof(arr[0]);? ????minAbsSumPair(arr, n);? ????return 0;? }? /* FOLLOWING FUNCTIONS ARE ONLY FOR? ???SORTING PURPOSE */ void exchange(int *a, int *b)? {? ????int temp;? ????temp = *a;? ????*a = *b;? ????*b = temp;? }? int partition(int arr[], int si, int ei)? {? ????int x = arr[ei];? ????int i = (si - 1);? ????int j;? ????for (j = si; j <= ei - 1; j++)? ????{? ????????if(arr[j] <= x)? ????????{? ????????????i++;? ????????????exchange(&arr[i], &arr[j]);? ????????}? ????}? ????exchange (&arr[i + 1], &arr[ei]);? ????return (i + 1);? }? /* Implementation of Quick Sort? arr[] --> Array to be sorted? si --> Starting index? ei --> Ending index? */ void quickSort(int arr[], int si, int ei)? {? ????int pi; /* Partitioning index */ ????if(si < ei)? ????{? ????????pi = partition(arr, si, ei);? ????????quickSort(arr, si, pi - 1);? ????????quickSort(arr, pi + 1, ei);? ????}? }? // This code is contributed by rathbhupendra ```