西安未央区做网站网站建设语言学什么

西安未央区做网站,网站建设语言学什么,新建南昌网站建设公司,wordpress mx主题VIP一、思路#xff1a;1.为方便双指针以及跳过相同元素#xff0c;先把nums排序。2.枚举nums[i]#xff0c;将问题转化成nums[j] nums[k] -nums[i]#xff0c;转变成两数之和的问题。3.题目要求答案中不能有重复的三元组#xff0c;因此要避免重复。#xff08;1#xf…一、思路1.为方便双指针以及跳过相同元素先把nums排序。2.枚举nums[i]将问题转化成nums[j] nums[k] -nums[i]转变成两数之和的问题。3.题目要求答案中不能有重复的三元组因此要避免重复。1在外层循环中如果发现nums[i] nums[i - 1]那么nums[i]与后面两个数组成的和为0的三元组nums[i - 1]也能组成一模一样的三元组这就重复了。所以遇到nums[i] nums[i - 1]的情况直接continue。2在内层循环中当三数之和等于0时为避免把相同的三元组计入答案跳过后续相同的nums[j]和nums[k]也可以只跳过相同的nums[j]。二、优化1.优化一如果nums[i]与后面最小的两个数相加nums[i] nums[i 1] nums[i 2] 0那么后面不可能存在三数之和等于0break外层循环终止循环执行循环后面的代码。2.优化二如果nums[i]与后面最大的两个数相加nums[i] nums[n - 2] nums[n - 1] 0那么内层循环不可能存在三数之和等于0但继续枚举nums[i]可以变大所以后面还有机会找到三数之和等于0continue外层循环跳过本次迭代进入下一次循环迭代。三、复杂度分析1.时间复杂度O(n^2)其中n为nums的长度。排序O(logn)外层循环枚举第一个数做法是O(n)双指针所以总的时间复杂度为O(n^2)。2.空间复杂度O(1)。附代码class Solution { public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger res new ArrayList(); int n nums.length; for(int i 0;i n - 2;i){ int x nums[i]; if(i 0 x nums[i - 1]){ //跳过重复数字 continue; } if(x nums[i 1] nums[i 2] 0){ //优化1 break; } if(x nums[n - 2] nums[n - 1] 0){ //优化2 continue; } int j i 1; int k n - 1; while(j k){ int sum x nums[j] nums[k]; if(sum 0){ k--; }else if(sum 0){ j; }else{ //三数之和为0 res.add(List.of(x,nums[j],nums[k])); //数组已经排序相同的数字会相邻需跳过重复数字 j; k--; //跳过重复数字 while(j k nums[j] nums[j - 1]){ j; } //跳过重复数字 while(k j nums[k] nums[k 1]){ k--; } } } } return res; } }