# 在两个数组中找到具有最小和的 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; } ```