C++实现三数之和 |21xrx.com

C++实现三数之和

2023-07-05 05:22:54 深夜i -- --

C++ 实现三数之和

在算法和数据结构中，三数之和是一种常见的问题。给定一个整数数组，找到三个数字，它们的和等于0。C++作为一种高效的编程语言，可以非常容易地实现这个问题的解决方案。

首先，我们需要先对输入的整数数组进行排序，这样可以帮助我们减少重复计算的次数。对于排序算法，可以使用C++中的STL库中的排序函数sort。

接下来，我们需要使用两个指针来找到三数之和为0的所有可能组合。我们可以使用一个外层循环来遍历整个数组，并固定第一个数字。然后，我们使用两个指针(左右指针)从排好序的数组的左右两侧同时向中间移动，并对它们指向的数字进行求和。如果和小于目标值，则我们把左指针往右移动一个位置；如果和大于目标值，则我们把右指针往左移动一个位置；如果和等于目标值，我们就找到了一组解。我们把这个解存储在一个容器中，并继续找不同的解，直到左指针大于等于右指针。

最后，我们返回容器中找到的所有解即可。

下面是C++代码实现：


class Solution {
public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end()); //对数组升序排序
    int n = nums.size();
    if (n < 3) return res; //特判
    for (int i = 0; i < n - 2; i++) { //第一个数字从左往右开始固定
      if (nums[i] > 0) break; //如果当前数字大于0，那么三数之和不可能等于0
      if (i > 0 && nums[i] == nums[i-1]) continue; //去除重复的数字
      int left = i + 1, right = n - 1; //左右指针分别指向当前数字之后的数字和最后一个数字
      while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];
        if (sum == 0) {
          res.push_back({nums[i], nums[left], nums[right]});
          while (left < right && nums[left] == nums[left+1]) left++; //去除左指针重复数字
          while (left < right && nums[right] == nums[right-1]) right--; //去除右指针重复数字
          left++; right--;
        }
        else if (sum < 0) left++; //和小于0，左指针右移
        else right--; //和大于0，右指针左移
      }
    }
    return res;
  }
};

在这个实现中，我们使用了STL的vector容器来存储解决方案，sort函数对数组进行排序。

总结：在本篇文章中，我们介绍了如何使用C++来实现三数之和问题的解决方案。我们使用了两个指针来定位解决方案，使用了STL库的sort函数来对数组排序。这个实现在时间和空间复杂度上都非常高效，是在算法和数据结构中解决这类问题的常见实践。

上一篇: idea打包java可执行jar包

下一篇: C++数组倒序排序

评论区

()

相似文章