欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 焦点 > LeetCode15.三数之和

LeetCode15.三数之和

2025/2/24 10:25:59 来源:https://blog.csdn.net/2301_79184547/article/details/142833554  浏览:    关键词:LeetCode15.三数之和

题目链接:15. 三数之和 - 力扣(LeetCode)

1.常规解法(会超时)

由于这道题需要排除相同的三元组,则可以先将目标数组从小到大排序,再遍历数组找到每个符合条件的三元组,若结果中不包含该三元组,就将该结果添加到目标结果中,代码如下:

    public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> 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) {List<Integer> 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,再定义一个顺序表存放三元组。

定义三个指针left,right,p,先将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 List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> 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 {List<Integer> 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;}

 希望大家积极指出不足之处

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词