CSP-J/S冲奖第18天：真题解析

解题步骤

读取输入：首先读取整数n，然后读取n个正整数并存储在一个数组或容器中。

排序数组：对数组进行排序，以便后续使用双指针法高效查找。

遍历数组：对于每个数target，检查是否存在另外两个不同的数a和b，使得a + b = target。

双指针查找：对于每个target，使用双指针法在已排序的数组中查找是否存在a和b满足条件。

计数结果：统计满足条件的target的数量。

涉及的知识点

数组操作：包括读取、存储和遍历数组。

排序算法：对数组进行排序，常用的是std::sort。

双指针技巧：用于在有序数组中高效查找满足特定条件的元素对。

条件判断与计数：通过条件判断来统计满足要求的元素数量。

正确代码参考

#include <bits/stdc++.h>

using namespace std;

int main() {

  int n;

  cin >> n;

  vector<int> nums(n);

  for (int i = 0; i < n; ++i) {

      cin >> nums[i];

  }

  // 对数组进行排序

  sort(nums.begin(), nums.end());

  int count = 0;

  for (int i = 0; i < n; ++i) {

      int target = nums[i];

      int left = 0, right = n - 1;

      while (left < right) {

          if (left == i) {

              left++;

              continue;

          }

          if (right == i) {

              right--;

              continue;

          }

          int sum = nums[left] + nums[right];

          if (sum == target) {

              count++;

              break;

          } else if (sum < target) {

              left++;

          } else {

              right--;

          }

      }

  }

  cout << count << endl;

  return 0;

}

代码解析

读取输入：使用cin读取整数n和n个正整数，并存储在vector<int>中。

排序数组：使用std::sort对数组进行升序排序。

遍历数组：使用for循环遍历每个数target。

双指针查找：使用两个指针left和right，分别从数组两端向中间移动，查找是否存在a和b满足a + b = target。

条件判断与计数：如果找到满足条件的a和b，则计数器count加1，并跳出当前循环。

注意事项

在双指针查找过程中，需要跳过与target相同的索引位置，以确保a和b是不同的数。

使用break语句跳出内层循环，避免重复计算。