网站设计知名企业,免费看行情的软件大全下载,做网站优化选阿里巴巴还是百度,工作15. 三数之和
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
**注意#xff1a;**答案中不可以包含重复…15. 三数之和
给你一个整数数组 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^5 nums[i] 10^5
题解
这个问题是典型的 “三数之和” 问题在算法设计和分析中它可以通过多种方法解决。给定一个整数数组 nums目标是找出所有不重复的三元组 [nums[i], nums[j], nums[k]]使得它们的和为 0。下面是解决这个问题的一种方法
排序: 首先对数组进行排序。排序是很重要的一步因为它使得在后续步骤中能够应用双指针技术来减少时间复杂度。使用双指针: 对于数组中的每一个元素 nums[i]设置两个指针一个指向 i 之后的第一个元素另一个指向数组的最后一个元素。检查三个元素的和与 0 的关系根据情况移动指针。去重: 在遍历的过程中需要跳过那些重复的元素以避免出现重复的三元组。
具体算法步骤如下 对数组 nums 进行排序。 遍历排序后的数组对于每一个元素 nums[i] 如果 nums[i] 大于 0则后面不可能有三个数加和等于 0结束循环。如果 nums[i] 与前一个元素相同则跳过这个元素避免重复。设置两个指针 left i 1 和 right nums.length - 1。当 left right 时执行以下操作 如果 nums[i] nums[left] nums[right] 0找到了一个解。记录这个三元组然后跳过所有重复的 nums[left] 和 nums[right]。如果和小于 0移动左指针 left。如果和大于 0移动右指针 right。 返回所有找到的三元组。
下面是这个算法的 C 实现
#include vector
#include algorithmstd::vectorstd::vectorint threeSum(std::vectorint nums) {std::sort(nums.begin(), nums.end());std::vectorstd::vectorint result;for (int i 0; i nums.size() nums[i] 0; i) {if (i 0 || nums[i] ! nums[i - 1]) {int left i 1, right nums.size() - 1;while (left right) {int sum nums[i] nums[left] nums[right];if (sum 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) {left;} else {--right;}}}}return result;
}这个算法的时间复杂度是 O(n^2)其中 n 是数组 nums 的长度。这是因为外层循环遍历了数组一次而内层的双指针遍历也是线性的。由于使用了排序整个算法的时间复杂度还包括排序的时间复杂度 O(n log n)。因此总的时间复杂度是 O(n log n n^2)在大多数情况下这主要由 O(n^2) 决定。
