wordpress 应用商店,seo技术交流,该网站正在紧急升级维护中,php网站开发事例题目链接#xff1a;15. 三数之和 - 力扣#xff08;LeetCode#xff09;
1.常规解法#xff08;会超时#xff09;
由于这道题需要排除相同的三元组#xff0c;则可以先将目标数组从小到大排序#xff0c;再遍历数组找到每个符合条件的三元组#xff0c;若结果中不包…题目链接15. 三数之和 - 力扣LeetCode
1.常规解法会超时
由于这道题需要排除相同的三元组则可以先将目标数组从小到大排序再遍历数组找到每个符合条件的三元组若结果中不包含该三元组就将该结果添加到目标结果中代码如下 public ListListInteger threeSum(int[] nums) {ListListInteger ret new ArrayList();Arrays.sort(nums);int n nums.length;for (int i 0; i n - 2; i) {for (int j i 1; j n - 1; j) {for (int k j 1; k n; k) {if (nums[i] nums[j] nums[k] 0) {ListInteger list new ArrayList();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);if (!ret.contains(list)) {ret.add(list);}}}}}return ret;}
2. 双指针算法
和常规解法一样我们要先将目标数组从小到大排序由于要求三数之和等于0我们可以先固定一个数只需找到剩下的哪两个数与这个数的和为0再定义一个顺序表存放三元组。
定义三个指针leftrightp先将p固定在最后一个数left在第一个数的位置right在倒数第二个数的位置接下来在每一轮循环中保持p不动只要移动left和right即可。
当nums[left] nums[right] nums[p] 0由单调性知若保持right不动left右边的数均大于left指向的数导致三数之和只会越加越大数组是从大到小排序的这时就要将right向左移动一位当nums[left] nums[right] nums[p] 0由单调性知若保持left不动right左边的数均小于right指向的数导致三个数之和会越加越小这是就要将left向右移动一位当nums[left] nums[right] nums[p] 0就要将这个结果添加到顺序表中由于最后的结果不允许出现相同的三元组这时就要去重。
去重若使用contains判断三元组是否重复代码就会超时这时我们就要在nums[left] nums[right] nums[p] 0时将与left和right指向的数的相同的数去掉由于这个数组是有序的那么相同的数就会聚集在一起只需要使用while循环去重即可相同的当left与right相遇时第一轮循环结束也去要进行去重操作将与p指向的数相同的数跳过即可。
优化当p指向的元素小于0时由单调性知p左边的元素均小于0就不存在三个数之和为0的情况直接返回结果即可。
流程图与代码如下 public ListListInteger threeSum(int[] nums) {ListListInteger ret new ArrayList();Arrays.sort(nums);int n nums.length;int p n - 1;while (p 1) {int left 0;int right p - 1;if (nums[p] 0) {return ret;}while (left right) {if (nums[left] nums[right] nums[p] 0) {left;} else if (nums[left] nums[right] nums[p] 0) {right--;} else {ListInteger list new ArrayList();list.add(nums[left]);list.add(nums[right]);list.add(nums[p]);ret.add(list);int numLeft nums[left];while (nums[left] numLeft left right) {left;}int numRight nums[right--];while (nums[right] numRight left right) {right--;}}}int numP nums[p--];while (nums[p] numP p 1) {p--;}}return ret;} 希望大家积极指出不足之处
