当前位置：首页 > news >正文

LeetCode 算法：三数之和c++

news 来源：原创 2024/9/29 13:31:41

原题链接🔗：
难度：中等⭐️⭐️

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

题解

排序+双指针解法

题解:

LeetCode上的“三数之和”问题要求找出数组中所有唯一的三元组，使得它们的和等于零。这是一个典型的搜索问题，可以通过排序加双指针的策略来解决。
下面是详细的解题思路：

排序：首先对数组进行排序。这不仅使得问题简化，还有助于后续跳过重复元素。

遍历数组：使用一个外层循环遍历数组，每次选择一个元素 nums[i] 作为三元组的第一个数。

双指针：对于选定的 nums[i]，初始化两个指针 left 和 right。left 指向 i + 1，right 指向数组的最后一个元素。

搜索和为零的三元组：

如果 nums[i]、nums[left] 和 nums[right] 的和为零，找到了一个三元组。
如果和小于零，意味着需要增大和，因此将 left 指针向右移动（选择更大的数）。
如果和大于零，意味着需要减小和，因此将 right 指针向左移动（选择更小的数）。

跳过重复元素：为了避免重复的三元组，当 left 和 left + 1 或者 right 和 right - 1 指向相同元素时，需要移动 left 或 right 指针跳过这些重复元素。

添加到结果集：每当找到和为零的三元组，就将其添加到结果集中。

继续搜索：更新 left 和 right 指针，继续搜索直到 left 和 right 相遇。

返回结果：返回所有找到的三元组组成的集合。

复杂度：时间复杂度O(N²)，空间复杂度O(logN)。
代码过程：

threeSum 函数接受一个整数数组 nums 作为输入，并返回所有唯一的三元组，使得它们的和等于零。

函数首先检查数组的大小是否至少为3，如果不是，则直接返回空结果。

对数组进行排序，以便使用双指针技巧。

使用一个 for 循环遍历数组，对于每个元素 nums[i]，尝试找到两个其他元素，使得它们的和与 nums[i] 相加等于零。

在 for 循环内部，使用两个指针 left 和 right 来找到和为零的三元组。

如果找到和为零的三元组，则将其添加到结果中，并跳过任何重复的元素。

main 函数提供了两个示例数组 nums1 和 nums2，调用 threeSum 函数，并打印出所有找到的三元组

c++ demo：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 函数用于找出所有和为0的三元组
vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;if (nums.size() < 3) return result;// 对数组进行排序sort(nums.begin(), nums.end());// 遍历数组for (int i = 0; i < nums.size() - 2; ++i) {// 跳过重复的元素if (i > 0 && nums[i] == nums[i - 1]) continue;// 使用双指针int left = i + 1, right = nums.size() - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {// 找到和为0的三元组result.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) {// 如果和小于0，移动左指针left++;}else {// 如果和大于0，移动右指针right--;}}}return result;
}int main() {// 示例输入vector<int> nums1 = { -1, 0, 1, 2, -1, -4 };vector<int> nums2 = { 0, 0, 0 };// 调用 threeSum 函数并打印结果auto result1 = threeSum(nums1);auto result2 = threeSum(nums2);cout << "Three sums of nums1: " << endl;for (const auto& triplet : result1) {for (int num : triplet) {cout << num << " ";}cout << endl;}cout << endl;cout << "Three sums of nums2: " << endl;for (const auto& triplet : result2) {for (int num : triplet) {cout << num << " ";}cout << endl;}return 0;
}