21xrx.com
2025-04-14 14:07:30 Monday
文章检索 我的文章 写文章
C++编程：求两数之和小于给定值n
2023-07-02 19:19:09 深夜i     12     0
C++ 数学 算法 运算符 循环

近年来，C++编程已经成为了计算机专业最重要的学科之一。而在C++编程中，求两数之和小于给定值n也是常见的编程问题之一。在本文中，我将介绍如何使用C++编写程序来解决这一问题。

首先，我们需要明确问题的具体要求。这个问题给定一个数组和一个目标值n，要求找出数组中所有的两个数的组合，使得这两个数之和小于n。接下来，我们可以考虑使用暴力枚举的方法来解决这个问题。

具体地说，我们可以使用双重循环遍历所有的数对，然后判断这两个数之和是否小于目标值n。如果是，就输出这两个数。代码如下：

#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int> > solve(vector<int>& nums, int target) {
  vector<pair<int, int> > res;
  for (int i = 0; i < nums.size(); i++) {
    for (int j = i + 1; j < nums.size(); j++) {
      if (nums[i] + nums[j] < target) {
        res.push_back(make_pair(nums[i], nums[j]));
      }
    }
  }
  return res;
}
int main() {
  int n, target;
  cin >> n >> target;
  vector<int> nums(n);
  for (int i = 0; i < n; i++) {
    cin >> nums[i];
  }
  vector<pair<int, int> > res = solve(nums, target);
  for (int i = 0; i < res.size(); i++) {
    cout << res[i].first << " " << res[i].second << endl;
  }
  return 0;
}

在此程序中，我们使用了C++中的vector容器来存放答案。其中，vector >表示一个由两个int类型组成的pair的动态数组，make_pair用来构造一个pair。最后我们使用循环输出所有符合要求的数对。显然，暴力枚举的时间复杂度是O(n^2)，对于很大的输入数据，会非常缓慢。

接下来，我们可以考虑使用排序和双指针的方法来优化代码。我们可以对数组进行从小到大的排序，然后使用双指针来找到符合要求的数对。具体来说，我们可以让左右指针分别指向数组的第一个元素和最后一个元素，然后判断这两个数之和是否小于目标值n。如果是，就输出这两个数，并将左指针右移一位；否则，将右指针左移一位。当左指针和右指针相遇时，就结束搜索。代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int> > solve(vector<int>& nums, int target) {
  vector<pair<int, int> > res;
  sort(nums.begin(), nums.end()); // 对数组进行排序
  int left = 0, right = nums.size() - 1;
  while (left < right) { // 使用双指针
    if (nums[left] + nums[right] < target) {
      for (int i = left + 1; i <= right; i++) {
        res.push_back(make_pair(nums[left], nums[i]));
      }
      left++;
    } else
      right--;
    
  }
  return res;
}
int main() {
  int n, target;
  cin >> n >> target;
  vector<int> nums(n);
  for (int i = 0; i < n; i++) {
    cin >> nums[i];
  }
  vector<pair<int, int> > res = solve(nums, target);
  for (int i = 0; i < res.size(); i++) {
    cout << res[i].first << " " << res[i].second << endl;
  }
  return 0;
}

在此程序中，我们使用了C++中的sort函数来对数组进行排序，时间复杂度为O(nlogn)。然后我们使用双指针来遍历数组，时间复杂度为O(n)。因此，该算法的总时间复杂度为O(nlogn)。相比暴力枚举，时间复杂度得到了极大的优化，对于大规模的数据输入，应该可以快速得到答案。

总之，本文介绍了使用C++编程求两数之和小于给定值n的方法。从暴力枚举到排序和双指针，我们一步步优化算法，使得程序的执行效率得到了很大的提升。C++编程虽然有一定的难度，但随着我们的学习和实践，相信我们能够顺利掌握这门学科，为未来的计算机工作打下坚实的基础。

  
  

评论区