网站收录突然全部没有了,不死鸟分享友情链接,西安网站建设公,兴平网站开发15.三数之和 注意#xff1a;最后答案中不能包含重复的三元组 使用排序双指针
可以使用三重循环枚举三元组#xff0c;但是需要哈希表进行去重操作#xff0c;得到不包含重复三元组的最终答案#xff0c;消耗量大量的时间和空间
对于不重复的本质#xff0c;保持三重循环…15.三数之和 注意最后答案中不能包含重复的三元组 使用排序双指针
可以使用三重循环枚举三元组但是需要哈希表进行去重操作得到不包含重复三元组的最终答案消耗量大量的时间和空间
对于不重复的本质保持三重循环的大框架不变只需要保证
第二重循环枚举到的元素不小于当前第一重循环枚举到的元素第三重循环枚举到的元素不小于当前第二重循环枚举到的元素
也就是说我们枚举到的三元组(a,b,c)满足a≤b≤c保证了只有(a,b,c)这个顺序会被枚举到而(b,a,c)和(c,b,a)这些不会这样就减少了重复要实现这一点可以将数组中的元素从小到大进行排序
同时保证在每一重循环中相邻两次枚举的元素不相同避免重复
此时时间复杂度仍未 O ( N 3 ) O(N^3) O(N3)仍然没有跳出三重循环的大框架因此继续优化进一步如果我们固定了前两重循环枚举到的元素a和b那么只有唯一的c满足abc0,当第二重循环往后枚举一个元素b’时由于b’b,那么满足ab’c’0的c’一定有c’c即c‘在数组中一定出现在c的左侧也就是说我们可以从小到大枚举b同时从大到小枚举c即第二重循环和第三重循环实际上是并列的关系这就是双指针当我们需要枚举数组中的两个元素时如果我们发现随着第一个元素的递增第二个元素是递减的那么就可以使用双指针的方法将枚举的时间复杂度从 O ( N 2 ) O(N^2) O(N2)减少至 O ( N ) O(N) O(N)
class Solution {public ListListInteger threeSum(int[] nums) {int n nums.length;Arrays.sort(nums); //先对数组进行排序ListListInteger ans new ArrayListListInteger();//枚举afor(int first 0;first n; first){//需要和上一次枚举的数不相同只有和上一次枚举的元素不相同时才会进行枚举if(first 0 nums[first] nums[first - 1]){continue;}// c对应的指针指向数组的最右端int third n - 1;int target -nums[first];// 枚举bfor(int second first 1;secondn;second){//同样需要和上一次枚举的元素不相同if(second first 1 nums[second] nums[second -1]){continue;}//保证b的指针在c的指针的左侧while(second third nums[second] nums[third] target){--third;}//如果指针重合随着b后续的增加// 就不会有满足abc0并且bc了可以退出循环if(second third){break;}if(nums[second] nums[third] target){ListInteger list new ArrayListInteger();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}}
