安徽建设局网站,图书馆管理系统,长春做网站要多少钱,购物网站网页设计图片题目#xff1a;盛最多水的容器
描述#xff1a; 给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意…题目盛最多水的容器
描述 给你一个整数数组 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] 。 注意输出的顺序和三元组的顺序并不重要。 leetcode链接 方法一 在原数组无序的两数之和中由于输出的是元素的下标所以我们不能够用排序双指针的方法因为会打破元素本来的位置而此题只需要输出元素即可无需输出元素的下标因此我们可以先进行排序再利用双指针的方法,但此题为三数之和我们考虑我们先确定第一个数那么找其它两个数就相当于找target和为0-num[i]第一个数的两个数这样就转变成了两数之和对于第一个数我们枚举出数组前n-2个数作为第一个数的情况然后在第一个数的后面用双指针的方法找出两数之和为target的其它两个数。 但是这样做出来的答案会有重复的三元组那我们如何避免重复的问题呢事实上我们对于第一个数如果此时确定的第一个数和上一次确定的第一个数相同那么我们后面找出来的答案肯定也会重复所以我们跳过相同的第一个数同样的对于第二个数我们在第一个数确定的情况下也要跳过和上一次确定相同的第二个数这样就能够保证答案三个数不会是之前出现过的三个数字。 时间复杂度o(n²) 第一个数字枚举的时间为o(n),后面双指针的时间为o(n),总共的时间复杂度为on² 空间复杂度o(logn)快速排序的空间复杂度为o(logn) vectorvectorint threeSum(vectorint nums) {vectorvectorint ans;int n nums.size();sort(nums.begin(),nums.end());for(int i0;in-2;i){int left i1,right n-1;int target 0-nums[i];if(i0nums[i]nums[i-1]){continue;}while(leftright){if(lefti1nums[left]nums[left-1]){left;continue;}if(nums[left]nums[right]target){ans.push_back({nums[i],nums[left],nums[right]});}nums[left]nums[right]target?right--:left;}}return ans;
}
