力扣 15 三数之和

作者 : 开心源码 本文共761个字,预计阅读时间需要2分钟 发布时间: 2022-05-13 共237人阅读

题意:在一个数组中找出3个和为0的数

思路:假设数组长度为n

  1. 把数组排序
  2. 外层遍历数组,index从0到n-2
  3. 内层遍历,从首指针到尾指针的数字,其中首指针初始化为外层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 三数之和

发表回复