频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
leetcode题目解答
2017-03-09 09:15:00           
收藏   我要投稿

leetcode题目解答:求3个数和为0,只需要固定其中一个数,使另外两个数的和为该数的相反数即可。

public class ThreeSum {

    /*
     * 先排序,然后左右夹逼。时间复杂度o(n^2) 
     * 先固定一个值,然后计算另外两个值相加是否为这个值的相反数即可。
     * 可以推广到k-sum,只需要k-2次循环,在最内层循环左右夹逼。
     */
    private List> res = new ArrayList<>();
    public List> threeSum(int[] nums) {

        if(nums==null || nums.length<3) return res;
        Arrays.sort(nums);
        //每次固定nums[i] 首尾指针分别i+1和nums.length-1.故i最多只能到i-3
        for(int i=0;i0 && nums[i]==nums[i-1]) continue;//i-1已经比较过了
            helper(nums,i+1,nums.length-1,nums[i]); //首指针从i+1开始,避免结果集的重复
        }
        return res;
    }

    private void helper(int[] nums, int start, int end, int target) {
        int i=start,j=end;
        while(i list = new ArrayList();
                list.add(target);
                list.add(nums[i]);
                list.add(nums[j]);
                res.add(list); //放入结果集中
                while(i
        
   
点击复制链接 与好友分享!回本站首页
上一篇:自己简单定义类的方法
下一篇:logback配置显示类名、方法名和代码行号
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站