大型网站是用哪种数据库做的,中国工厂网下载,江苏中星建设集团网站,一个网站的建设需要哪些流程优质博文#xff1a;IT-BLOG-CN 一、题目
给你一个整数数组nums#xff0c;判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k#xff0c;同时还满足nums[i] nums[j] nums[k] 0。请你返回所有和为0且不重复的三元组。 注意#xff1a;答案中不可以… 优质博文IT-BLOG-CN 一、题目
给你一个整数数组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 二、代码
排序 双指针 题目中要求找到所有「不重复」且和为0的三元组这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下数组中的元素全部为0即[0,0,0,0,0]任意一个三元组的和都为0。如果我们直接使用三重循环枚举三元组会得到O(N3)个满足题目要求的三元组其中N是数组的长度时间复杂度至少为O(N3)。在这之后我们还需要使用哈希表进行去重操作得到不包含重复三元组的最终答案又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高因此我们要换一种思路来考虑这个问题。
「不重复」的本质是什么我们保持三重循环的大框架不变只需要保证第二重循环枚举到的元素不小于当前第一重循环枚举到的元素第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
也就是说我们枚举的三元组(a,b,c)满足a≤b≤ca保证了只有(a,b,c)这个顺序会被枚举到而(b,a,c)(c,b,a)等等这些不会这样就减少了重复。要实现这一点我们可以将数组中的元素从小到大进行排序随后使用普通的三重循环就可以满足上面的要求。同时对于每一重循环而言相邻两次枚举的元素不能相同否则也会造成重复。举个例子如果排完序的数组为[]1,2,2,2,4]
nums.sort()
for first 0 .. n-1// 只有和上一次枚举的元素不相同我们才会进行枚举if first 0 or nums[first] ! nums[first-1] thenfor second first1 .. n-1if second first1 or nums[second] ! nums[second-1] thenfor third second1 .. n-1if third second1 or nums[third] ! nums[third-1] then// 判断是否有 abc0check(first, second, third)这种方法的时间复杂度仍然为O(N3)毕竟我们还是没有跳出三重循环的大框架。然而它是很容易继续优化的可以发现如果我们固定了前两重循环枚举到的元素a和b那么只有唯一的c满足abc0。当第二重循环往后枚举一个元素b时由于b′b那么满足ab′c′0的c′一定有c′c即c′在数组中一定出现在c的左侧。也就是说我们可以从小到大枚举b同时从大到小枚举c即第二重循环和第三重循环实际上是并列的关系。
有了这样的发现我们就可以保持第二重循环不变而将第三重循环变成一个从数组最右端开始向左移动的指针从而得到下面的伪代码
nums.sort()
for first 0 .. n-1if first 0 or nums[first] ! nums[first-1] then// 第三重循环对应的指针third n-1for second first1 .. n-1if second first1 or nums[second] ! nums[second-1] then// 向左移动指针直到 abc 不大于 0while nums[first]nums[second]nums[third] 0third third-1// 判断是否有 abc0check(first, second, third)这个方法就是我们常说的「双指针」当我们需要枚举数组中的两个元素时如果我们发现随着第一个元素的递增第二个元素是递减的那么就可以使用双指针的方法将枚举的时间复杂度从O(N2)减少至O(N)。为什么是O(N)呢这是因为在枚举的过程每一步中「左指针」会向右移动一个位置也就是题目中的b而「右指针」会向左移动若干个位置这个与数组的元素有关但我们知道它一共会移动的位置数为O(N)均摊下来每次也向左移动一个位置因此时间复杂度为O(N)。
注意到我们的伪代码中还有第一重循环时间复杂度为O(N)因此枚举的总时间复杂度为O(N2)。由于排序的时间复杂度为O(NlogN)在渐进意义下小于前者因此算法的总时间复杂度为O(N2)。
上述的伪代码中还有一些细节需要补充例如我们需要保持左指针一直在右指针的左侧即满足b≤c具体可以参考下面的代码均给出了详细的注释。
class Solution {public ListListInteger threeSum(int[] nums) {//思想1、先对 nums 进行排序// 2、先确定第一层循环通过 0 - nums[x] 得到第二层和第三层的和// 3、将第二层和第三层汇总为一层left i 1; right nums.length - 1; 进行双指针移动计算和如果相等加入队列并继续移动指针直到不满足 left rightint left 0, right 0, size 0;ListListInteger res new ArrayList();Arrays.sort(nums);for(int i 0; i nums.length; i) {if (i 0 i nums.length nums[i] nums[i-1]) {continue;}// i 发生变化之后left 和 right 指针都需要发生变化。 第一次将right定义再外部导致bugleft i 1;right nums.length - 1;int tar -nums[i];while(left right) {if (nums[left] nums[right] tar) {ListInteger temp Arrays.asList(nums[i], nums[left], nums[right]);res.add(temp);// 数据去重while(left right nums[left] nums[left 1]) {left;}while(right left nums[right] nums[right - 1]) {--right;}left;--right;} else if(nums[left] nums[right] tar){left;} else {--right;}}}return res;}
}时间复杂度 O(N2)其中N是数组nums的长度。 时间复杂度 O(N2)其中N是数组nums的长度。
