欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 健康 > 养生 > 7.《双指针篇》---⑦三数之和(中等偏难)

7.《双指针篇》---⑦三数之和(中等偏难)

2025/4/2 20:05:02 来源:https://blog.csdn.net/m0_73456341/article/details/143567898  浏览:    关键词:7.《双指针篇》---⑦三数之和(中等偏难)

题目传送门 

方法一:双指针

1.新建一个顺序表用来返回结果。并排序数组。

2.for循环 i 从第一个数组元素遍历到倒数第三个数。

3.如果遍历过程中有值大于0的则break; 

4.定义左右指针,以及target。int left = i + 1, right = n - 1; int target = -nums[i];

5.类似两数之和。比较int sum = nums[l] + nums[r] 与 target的大小

注意:

1.不能返回重复的数组。因此我们还需要排除重复的。

2.排序之后。在sum = target的时候。我们进行 left 和 right的排重。

3.在 i++ 之后我们进行 num[i] 这个元素的排重。

注意:

排重的时候双指针排重记得 left < right。并且num【i】排重的时候注意 i<n-1。

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int n = nums.length-1;for(int i = 0; i < n-1; ){if(nums[i] > 0){break;}int left = i + 1;int right = n;int target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum == target){ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));left++;right--;while(left < right && nums[left] == nums[left-1]){left++;}while(left < right && nums[right] == nums[right+1]){right--;}}else if(sum < target){left++;}else{right--;}}i++;while(i<n-1 && nums[i] == nums[i-1]){i++;}}return ret;}
}

 复杂度分析

版权声明:

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

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

热搜词