两数之和笔记

对于一个非常庞大的数组，我们可以使用一些优化方法来寻找其中所有满足“两数之和不大于 `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)`，用于存储符合条件的数对。