# 在兩個數組中找到具有最小和的 k 對 > 原文： [https://www.geeksforgeeks.org/find-k-pairs-smallest-sums-two-arrays/](https://www.geeksforgeeks.org/find-k-pairs-smallest-sums-two-arrays/) 給定兩個按升序排序的整數數組`arr1[]`和`arr2[]`和一個整數`k`。 查找具有最小總和的`k`對，以使對中的一個元素屬于`arr1[]`而另一個元素屬于`arr2[]` 例子： ``` Input : arr1[] = {1, 7, 11} arr2[] = {2, 4, 6} k = 3 Output : [1, 2], [1, 4], [1, 6] Explanation: The first 3 pairs are returned from the sequence [1, 2], [1, 4], [1, 6], [7, 2], [7, 4], [11, 2], [7, 6], [11, 4], [11, 6] ``` **方法 1（簡單）** 1. 查找所有對并存儲其總和。 此步驟的時間復雜度為`O(n1 * n2)`，其中`n1`和`n2`是輸入數組的大小。 2. 然后根據總和對進行排序。 此步驟的時間復雜度為`O(n1 * n2 * log(n1 * n2))` 總時間復雜度：`O(n1 * n2 * log(n1 * n2))` **方法 2（有效）**： 我們從最小和對開始一個接一個地找到`k`個最小和對。 想法是跟蹤已經為每個元素`arr1[i1]`考慮過的`arr2[]`的所有元素，以便在迭代中我們僅考慮下一個元素。 為此，我們使用索引數組`index2[]`來跟蹤另一個數組中下一個元素的索引。 它僅表示在每次迭代中將第二個數組的哪個元素與第一個數組的元素相加。 我們為形成下一個最小值對的元素在索引數組中增加值。 ## C++ ```cpp // C++ program to prints first k pairs with least sum from two // arrays. #include<bits/stdc++.h> using namespace std; // Function to find k pairs with least sum such // that one elemennt of a pair is from arr1[] and // other element is from arr2[] void kSmallestPair(int arr1[], int n1, int arr2[], ???????????????????????????????????int n2, int k) { ????if (k > n1*n2) ????{ ????????cout << "k pairs don't exist"; ????????return ; ????} ????// Stores current index in arr2[] for ????// every element of arr1[]. Initially ????// all values are considered 0\. ????// Here current index is the index before ????// which all elements are considered as ????// part of output. ????int index2[n1]; ????memset(index2, 0, sizeof(index2)); ????while (k > 0) ????{ ????????// Initialize current pair sum as infinite ????????int min_sum = INT_MAX; ????????int min_index = 0; ????????// To pick next pair, traverse for all elements ????????// of arr1[], for every element, find corresponding ????????// current element in arr2[] and pick minimum of ????????// all formed pairs. ????????for (int i1 = 0; i1 < n1; i1++) ????????{ ????????????// Check if current element of arr1[] plus ????????????// element of array2 to be used gives minimum ????????????// sum ????????????if (index2[i1] < n2 && ????????????????arr1[i1] + arr2[index2[i1]] < min_sum) ????????????{ ????????????????// Update index that gives minimum ????????????????min_index = i1; ????????????????// update minimum sum ????????????????min_sum = arr1[i1] + arr2[index2[i1]]; ????????????} ????????} ????????cout << "(" << arr1[min_index] << ", " ?????????????<< arr2[index2[min_index]] << ") "; ????????index2[min_index]++; ????????k--; ????} } // Driver code int main() { ????int arr1[] = {1, 3, 11}; ????int n1 = sizeof(arr1) / sizeof(arr1[0]); ????int arr2[] = {2, 4, 8}; ????int n2 = sizeof(arr2) / sizeof(arr2[0]); ????int k = 4; ????kSmallestPair( arr1, n1, arr2, n2, k); ????return 0; } ```