网站改版新闻稿,jsp做门户网站,app网站开发小程序,小程序定制语言题目
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。
注意#xff1a;答案中不可以包含重复的三元组。 示…题目
给你一个整数数组 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-105 nums[i] 105
代码展示
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint 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) {left; // 和太小增加左边的数} else if (sum 0) {right--; // 和太大减少右边的数} else {// 找到一个解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--;}}}return result;}
};
写者心得
对于这一道题目我刚开始的想法就是用一个循环再加上一个超长的if循环解决这个问题。可是刚一开始调试if循环的条件就报了错。在学习请教的过程中我觉得这个代码有着以下的几个亮点
1.在设定动态数组的时候使用二维数组。我刚开始接触这个题目的时候我所设定的数组并没有考虑到二维数组。而题目要求的那个结果却是二维数组没有认出来这是我学识上的不足。
2.代码的第二步就对数组进行了排序一步的目的其实是为了之后使用双指针做铺垫,但是在我刚开始对于题目思考的时候也根本没有考虑到先将元素进行排序之后更容易得到数组前后两个数的和是否为0
3.如果在if循环中条件过多就应该考虑使用while循环。他说了我刚开始就是给if循环里面加了一大堆条件事实证明这样的路是走不通的。如果以后遇到了多条件的题目的时候就应该考虑使用while循环而不是在if循环里不断套用。
4.双指针它的精髓在于在数组中找三个数和为零的数字我在之前的编程中其实使用过双指针但是那时候我看的不太懂。现在我可以总结出双指针使用的情况应该就在于与前后两个数有关系的时候双指针能发挥很大的作用。
5.跳过重复元素。这一步看似平平无奇但其实是使用双指针至关重要的前提试想一下如果遇到重复的元素其输出的结果会对于我们对于整个代码的逻辑产生非常严重的影响。而且这样的困扰会一直伴随着我们对于代码的读写和思考
6.去重这一点是我根本就没有想到的或者说我的思路还没有到这一步但是代码用了两个while循环轻松解决了在得到目标数组之后如果在二维数组中这个数组与其他的数组重复的时候的问题。 代码解释
定义和初始化
vectorvectorint result;
这行代码创建了一个空的二维向量 result。每个内部的 vectorint 将会保存一个三元组。
添加元素
当你找到一个满足条件的三元组时你可以将其添加到 result 中
result.push_back({nums[i], nums[left], nums[right]});
这里的 {nums[i], nums[left], nums[right]} 是一个初始化列表它会被转换成一个 vectorint 并添加到 result 的末尾。
sort(nums.begin(), nums.end()); // 对数组进行排序
使用 sort 函数对输入数组 nums 进行升序排序。排序后可以通过双指针法有效地查找满足条件的三元组。
for (int i 0; i nums.size() - 2; i) {
开始一个外层循环遍历数组中的每一个元素作为第一个数 nums[i]。这里 i 的范围是从 0 到 nums.size() - 3因为还需要两个额外的位置来放置另外两个数。
if (i 0 nums[i] nums[i - 1]) continue; // 跳过重复元素
如果当前元素 nums[i] 与前一个元素相同则跳过本次循环避免产生重复的三元组。
int left i 1, right nums.size() - 1;
初始化两个指针 left 和 right分别指向当前元素 nums[i] 后的第一个位置和数组的最后一个位置。
while (left right) {
进入一个内层循环当 left 指针小于 right 指针时继续循环。
int sum nums[i] nums[left] nums[right];
计算当前三个指针所指向的元素之和 sum。
if (sum 0) {left; // 和太小增加左边的数
如果 sum 小于零说明当前和太小需要增大 left 指针所指向的数因此将 left 向右移动一位。
} else if (sum 0) {right--; // 和太大减少右边的数
如果 sum 大于零说明当前和太大需要减小 right 指针所指向的数因此将 right 向左移动一位。
} else {// 找到一个解result.push_back({nums[i], nums[left], nums[right]});
如果 sum 等于零说明找到了一个满足条件的三元组将其添加到结果列表 result 中。
while (left right nums[left] nums[left 1]) left; // 跳过重复的左指针
为了避免产生重复的三元组如果 left 指针所指向的数与下一个数相同则继续将 left 向右移动。
while (left right nums[right] nums[right - 1]) right--; // 跳过重复的右指针
同理如果 right 指针所指向的数与前一个数相同则继续将 right 向左移动。
left;
right--;
无论是否有重复的数都需要将 left 和 right 指针各向中间移动一位以便继续查找新的可能的三元组。
return result;
返回结果列表 result其中包含了所有满足条件的三元组。
