力扣 15 三数之和
题意:在一个数组中找出3个和为0的数
思路:假设数组长度为n
- 把数组排序
- 外层遍历数组,index从0到n-2
- 内层遍历,从首指针到尾指针的数字,其中首指针初始化为外层index+1,尾指针初始化为n-1,首尾指针移动条件可见代码注释
思想:数组排序+首尾指针
复杂度:时间O(n2),空间O(n2)
class Solution { public List<List<Integer>> threeSum(int[] nums) { int len = nums.length; Arrays.sort(nums); List<List<Integer>> res = new ArrayList(); for(int i=0;i<len-2;i++) { if(i>0 && nums[i] == nums[i-1]) continue; int s = i+1; int e = len-1; while(s<e) { // 求当前3个数的和 int sum = nums[i] + nums[s] + nums[e]; // 假如和为0 if(sum == 0) { // 加入结果集 res.add(Arrays.asList(nums[i], nums[s], nums[e])); // 跳过和当前尾指针数想等的数字,避免重复 int temp = nums[e]; while(e>s&&temp == nums[e]) e--; temp = nums[s]; // 跳过和当前首指针数想等的数字,避免重复 while(e>s&&temp == nums[s]) s++; } else if(sum > 0) { // 假如和大于0,移动尾指针,由于数组是排序的,所以后面的数字比前边大,向前移动尾指针可以减小和 e--; } else if(sum < 0) { // 假如和小于0,移动首指针,由于数组是排序的,所以后天的数字比前边大,向后移动首指针可以增大和 s++; } } } return res; }}说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 力扣 15 三数之和
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 力扣 15 三数之和