c++ - 如何不多次使用一个元素？

Question

所以问题来了：你输入 n(2 < n < 10^6); k(-10^9 < k < 10^9); n 个从 -10^9 到 10^9 的整数。目标是找出 n 个整数中有多少对，其中总和等于 k ​​并打印出来。您不能多次使用这些元素。整数可以重复。我的代码是：

#include <iostream>

using namespace std;

int main(){
    int n;
    int k;
    cin >> n;
    cin >> k;
    int numbers[n];
    for (int i = 0; i < n; i++){
        cin >> numbers[i];
    }
    int result = 0;
    for (int j = 0; j < n; j++){
         for (int l = j + 1; l < n; l++){
             if (numbers[j] + numbers[l] == k){
                 result += 1;
                 break;
             }
         }
     }
    cout << result;
    return 0;
}

你如何跳过使用过的元素？示例 1：输入：

5 4
2 2 2 2 2

输出应该是：2(因为 2+2, 2+2) 我的是：4(2+2, 2+2, 2+2, 2+2)

示例 2：输入：

5 4
1 3 5 2 -1

我的输出： 2(since 1+3=4, 5+(-1)=4)- 这是正确的 我唯一的问题是我不能跳过使用过的元素。

标签： c++

Answer 1

使用一个数组来保存一个元素是否已被使用（就像评论中提到的那样）：

#include <iostream>

using namespace std;

//array with 10^6 elements, 
//(== max number of numbers)
bool used[1000000];

int main(){
    int n;
    int k;
    cin >> n;
    cin >> k;
    int numbers[n];
    for (int i = 0; i < n; i++){
        cin >> numbers[i];
    }
    int result = 0;
    for (int j = 0; j < n; j++){
        //check if element has been used
         if(used[j] == 1) {
            continue;
         }
         for (int l = j + 1; l < n; l++){
            //check if element has been used
            if(used[l] == 1 ) {
                continue;
            }
             if (numbers[j] + numbers[l] == k){
                 //mark elements as used
                 used[j] = 1;
                 used[l] = 1;
                 result += 1;
                 break;
             }
         }
     }
    cout << result;
    return 0;
}