美文网首页
[Day0]1.Two Sum

[Day0]1.Two Sum

作者: Shira0905 | 来源:发表于2017-01-30 00:43 被阅读0次

    After much thought, I title it as "Day0" but not "Day1". This is not purely out of the custom of a CS student, also, it is because I regard it as an informal one and a simple test. (I have to admit that there is a little prejudice for zero.Hah~)
    Now, I am ready to plant a flag that I will solve at least one problem a day on Leetcode for next several(?) months. If, though I truly hope I can stick to this and publish everyday, if there is emergency, I will make up on other idle time!

    Today's problem is really a simple one. But in contrast, the top solution given by the website is a beautiful one. And the top solution only run 8 ms, which really surprised me.
    O(n) VS O(n*n)? To be honest, I don't know much of how to compute the complexity of the algorithm. ->_->

    public static int[] twoSum(int[] nums, int target) {
        int [] a=new int [2];
        for(int i=0;i<nums.length-1;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    a[0]=i;
                    a[1]=j;
                }
            }
        }
        return a;
    }
    
    public static int[] twoSumTop(int[] nums, int target) {
        int [] a=new int [2];
        Map<Integer, Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                a[0]=map.get(target-nums[i]);
                a[1]=i;
                return a;
            }
            map.put(nums[i], i);
        }
        return a;
    }

    相关文章

      网友评论

          本文标题:[Day0]1.Two Sum

          本文链接:https://www.haomeiwen.com/subject/qeocittx.html