我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
查看: 705|回复: 1
收起左侧

[Leetcode] 4Sum n2 解法 求java代码

[复制链接] |试试Instant~ |关注本帖
我的人缘0
oio14644 发表于 2015-9-22 11:41:13 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
4Sum  n2 解法 求java代码,作为参考

谢谢先

上一篇:谁给分析一下为什么树的前序遍历,空间复杂度是lgN?
下一篇:请教一下我这个解法怎么不对了--UVa 11418 Clever Naming Patterns
我的人缘0
hj867955629 发表于 2015-9-22 15:09:09 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
public class Solution {
    class Pair {
        int fir;
        int sec;
        public Pair(int fir, int sec) {
            this.fir = fir;
            this.sec = sec;
        }
    }
   
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 4) {
            return res;
        }
        HashMap<Integer, List<Pair>> hash = new HashMap<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i+1; j < nums.length; j++) {
                int sum = nums[i]+nums[j];
                if (!hash.containsKey(sum)) {
                    List<Pair> list = new ArrayList<>();
                    hash.put(sum, list);
                }
                hash.get(sum).add(new Pair(i, j));
            }
        }
        for (int i = 0; i < nums.length-3; i++) {
            if (i != 0 && nums[i] == nums[i-1]) {
                continue;
            }
            for (int j = i+1; j < nums.length-2; j++) {
                if (j != i+1 && nums[j] == nums[j-1]) {
                    continue;
                }
                int target1 = target-nums[i]-nums[j];
                if (!hash.containsKey(target1)) {
                    continue;
                }
                boolean firstAdd = true;
                for (Pair pair: hash.get(target1)) {
                    if (pair.fir <= j) {
                        continue;
                    }
                    if (firstAdd || nums[pair.fir] != res.get(res.size()-1).get(2)) {
                        firstAdd = false;
                        List<Integer> tmp = new ArrayList<>();
                        tmp.add(nums[i]);
                        tmp.add(nums[j]);
                        tmp.add(nums[pair.fir]);
                        tmp.add(nums[pair.sec]);
                        res.add(tmp);
                    }
                }
            }
        }
        return res;
    }
}
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-28 13:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表