如何避免重复使用元素？求两数和为k的不重复元素对数问题

我来帮你解决这个问题，你的代码现在有两个核心问题：一是没处理元素只能用一次的限制，二是效率太低没法处理大n的情况。咱们一步步来拆解和修复：

你的代码目前的问题在于：

• 元素重复计数：双层循环会遍历所有j < l的组合，只要和为k就计数，但没有标记元素是否已被使用。比如全是2的例子里，j=0会和l=1、2、3、4分别配对计数，j=1又会和l=2、3、4配对，最终得到4次，但实际上每个元素只能用一次，5个2最多组成2对。
• 时间复杂度爆炸：O(n²)的算法在n接近1e6时，运行时间会达到天文数字，完全无法通过时间限制。

另外还有两个隐藏问题：

• 用了非标准的变长数组int numbers[n]，这是GCC扩展，不是标准C++，移植性差；
• 没有处理整数溢出：两个int类型的1e9相加会超过int的范围，导致计算错误。

这个方法能同时解决元素复用和效率问题，时间复杂度为O(n log n)，完全适配n=1e6的场景，且能保证每个元素只被使用一次。

思路 #

1. 排序数组：先把数组从小到大排序，这样可以用双指针从两端向中间逼近，快速找到和为k的配对。
2. 双指针遍历：
   • 左指针从数组开头（最小元素）开始，右指针从数组末尾（最大元素）开始；
   • 如果两数之和等于k：计数加1，同时移动左右指针（这两个元素已经被使用，不能再参与其他配对）；
   • 如果和小于k：左指针右移，找更大的元素来凑和；
   • 如果和大于k：右指针左移，找更小的元素来凑和；
3. 终止条件：当左指针 >= 右指针时，停止遍历。

修改后的代码 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 加速输入输出，处理大n时必备
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    long long k; // 用long long避免溢出
    cin >> n >> k;
    
    // 用vector存储数组，替代非标准变长数组
    vector<long long> numbers(n);
    for (int i = 0; i < n; ++i) {
        cin >> numbers[i];
    }
    
    // 排序数组
    sort(numbers.begin(), numbers.end());
    
    long long result = 0;
    int left = 0, right = n - 1;
    
    while (left < right) {
        long long sum = numbers[left] + numbers[right];
        if (sum == k) {
            ++result;
            ++left;
            --right;
        } else if (sum < k) {
            ++left;
        } else {
            --right;
        }
    }
    
    cout << result << endl;
    return 0;
}

测试验证 #

• 示例1：输入5 4 2 2 2 2 2，排序后数组为[2,2,2,2,2]。遍历过程：
  • left=0, right=4 → sum=4 → result=1，left=1, right=3；
  • left=1, right=3 → sum=4 → result=2，left=2, right=2；
  • 循环终止，输出2，符合预期。
• 示例2：输入5 4 1 3 5 2 -1，排序后数组为[-1,1,2,3,5]。遍历过程：
  • left=0, right=4 → sum=-1+5=4 → result=1，left=1, right=3；
  • left=1, right=3 → sum=1+3=4 → result=2，left=2, right=2；
  • 循环终止，输出2，符合预期。

• 整数溢出处理：用long long存储元素和k，因为两个1e9的int相加会超过32位int的范围（-2^31到231-1），导致计算错误。
• 输入输出加速：ios::sync_with_stdio(false); cin.tie(nullptr);可以大幅提升大n下的输入速度，避免超时。

内容的提问来源于stack exchange，提问作者amgaa002