一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 361|回复: 1
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
oio14644 发表于 2015-9-22 11:41:13 | 显示全部楼层 |阅读模式

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

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

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

谢谢先
hj867955629 发表于 2015-9-22 15:09:09 | 显示全部楼层
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;
    }
}
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 14:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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