对于一个非常庞大的数组，我们可以使用一些优化方法来寻找其中所有满足“两数之和不大于 `n`” 的数对。直接使用双重循环会导致时间复杂度为 `O(N^2)`，这在数组庞大时可能会非常慢。这里我们可以使用 **双指针法** 来优化该问题，将时间复杂度降为 `O(N log N)`。
### 算法思路
1. **排序数组**：首先对数组进行升序排序，时间复杂度为 `O(N log N)`。
2. **双指针法**：
- 初始化两个指针 `left` 和 `right`，分别指向数组的起始和末尾。
- 如果 `arr[left] + arr[right] <= n`，则从 `left` 到 `right` 之间的所有数与 `arr[left]` 的和都满足要求，因为数组已排序。记录所有这些数对，并将 `left` 向右移动一位。
- 如果 `arr[left] + arr[right] > n`，则将 `right` 左移一位，尝试缩小数对的和。
3. 重复步骤2，直到 `left` 与 `right` 指针相遇。
### 示例代码
以下是C++实现的代码示例：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<std::pair<int, int>> findPairsWithSumLessThanN(std::vector<int>& arr, int n) {
std::vector<std::pair<int, int>> result;
// 对数组进行排序
std::sort(arr.begin(), arr.end());
int left = 0;
int right = arr.size() - 1;
while (left < right) {
// 检查当前两个数的和
if (arr[left] + arr[right] <= n) {
// 从 left 到 right 之间的所有数与 arr[left] 组成的数对都符合条件
for (int i = left + 1; i <= right; ++i) {
result.push_back({arr[left], arr[i]});
}
// 移动左指针
++left;
} else {
// 移动右指针
--right;
}
}
return result;
}
int main() {
std::vector<int> arr = {1, 3, 5, 7, 9};
int n = 10;
std::vector<std::pair<int, int>> result = findPairsWithSumLessThanN(arr, n);
std::cout << "Pairs with sum less than or equal to " << n << ":\n";
for (const auto& pair : result) {
std::cout << "(" << pair.first << ", " << pair.second << ")\n";
}
return 0;
}
```
### 代码说明
1. **排序数组**：先对数组进行排序，以便使用双指针法。
2. **双指针寻找数对**：
- 如果 `arr[left] + arr[right] <= n`，则从 `left + 1` 到 `right` 之间的所有元素与 `arr[left]` 的和都满足条件，记录这些数对。
- 如果 `arr[left] + arr[right] > n`，则将 `right` 左移一位，尝试找更小的数对。
3. **结果输出**：输出所有符合条件的数对。
### 复杂度分析
- **时间复杂度**：排序为 `O(N log N)`，双指针部分为 `O(N)`，总的时间复杂度为 `O(N log N)`。
- **空间复杂度**：`O(N)`，用于存储符合条件的数对。