网站建设基本流程详细说明,国内精美网站欣赏,seo短视频网页入口营销,免费个人名片生成器LeetCode 三数之和 — 改进解法 题目#xff1a;给定一个包含 n 个整数的数组 nums#xff0c;判断 nums 中是否存在三个元素 a#xff0c;b#xff0c;c #xff0c;使得 a b c 0 #xff1f;找出所有满足条件且不重复的三元组。 注意#xff1a;答案中不可以包含重…LeetCode 三数之和 — 改进解法 题目给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 找出所有满足条件且不重复的三元组。 注意答案中不可以包含重复的三元组。 例如, 给定数组 nums [-1, 0, 1, 2, -1, -4] 满足要求的三元组集合为[ [-1, 0, 1], [-1, -1, 2] ] 最开始做的解法是先将整个数组排序然后遍历前两个数(a和b)的所有情况(n^2)对于第三个数则从剩余的数中即从第二个数下一个位置开始到末尾利用二分查找出是否存在数字 -(ab)即可。 复杂度O(n^2·logn) class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger ans new ArrayListListInteger();Arrays.sort(nums);MapInteger,Integer mi new HashMap();for(int i0;inums.length-1;i) {if(mi.get(nums[i]) ! null) continue; //记录i下标读过的数字mi.put(nums[i],1);MapInteger,Integer mj new HashMap(); for(int ji1;jnums.length;j) {if(mj.get(nums[j]) ! null) continue; //记录j下标读过的数字mj.put(nums[j],1);int temp -(nums[i]nums[j]);if(bSearch(nums,j1,nums.length-1,temp) false) continue; //二分搜索j下标之后的区间是否有数字tempans.add(Arrays.asList(nums[i],nums[j],temp));}}return ans;}//二分算法public boolean bSearch(int[] nums,int s,int e,int key) {int starts,ende,mid;while(startend){mid (startend)/2;if(key nums[mid]) endmid-1;else if(key nums[mid]) startmid1;else if(key nums[mid]) return true;}return false;}
} 里面有两个用了哈希的地方所以时间复杂度应该还要乘上一个常数K...(解数组相关的题感觉总有些依赖哈希的方法_ ...) 最近做了另一个数组区间相关的题目受其解法的启发打算对这道题解法进行优化。 还是先对数组进行排序对第一个数字(a)进行遍历而然后在剩余的数中用前后指针的方法找出两个和为-a的数字两个指针left和rightleft初始化为数字a的下一位置right为最后一个位置。比较nums[left]nums[right]a和0的大小如果大于0则right--小于就left。 其中在添加结果集时需考虑去重问题用个哈希判断是否有重复就行了复杂度O(n^2·K) class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger ans new ArrayListListInteger();Arrays.sort(nums);MapInteger,Integer mi new HashMap();for(int i0;inums.length-2;i) {if(mi.get(nums[i]) ! null) continue; //记录i下标读过的数字mi.put(nums[i],1);MapInteger,Integer mj new HashMap();int l i1, r nums.length-1, temp;while(lr) {temp nums[i] nums[l] nums[r];if(temp 0) {l;} else if(temp 0) {r--;} else {if((mj.get(nums[l])) null) {ans.add(Arrays.asList(nums[i], nums[l], nums[r]));mj.put(nums[l], 1);}l; r--;}}}return ans;}
} 转载于:https://www.cnblogs.com/geek1116/p/10172313.html
