Java, O(nlogn), beats 98.85%


  • 25
    Y

    The general idea is:

    step1 : copy an array, and sort it using quick sort, O(nlogn)

    step2 : using start and end points to find a, b which satifys a+b==target, O(n)

    step3 : find the index of a, b from origin array, O(n)

    note: in step3, you should judge whethour a==b, if true, you must find the second index of b.

    if you have any higher efficiency solution, contact me, please.
    https://github.com/yangliguang

    As follows:

    //O(nlogn)
    	    public int[] twoSum_n2(int[] nums, int target) {
    	    	if(nums == null)
    	    		return null;
    	    	int[] nums2 = Arrays.copyOf(nums, nums.length);
    	    	Arrays.sort(nums2);
    	    	int a = 0, b = 0;
    	    	int start = 0, end = nums2.length-1;
    	    	//find two nums
    	    	while(start<end){
    	    		int sum = nums2[start] + nums2[end];
    	    		if(sum < target)
    	    			start++;
    	    		else if(sum > target)
    	    			end--;
    	    		else{
    	    			a = nums2[start]; b = nums2[end];
    	    			break;
    	    		}
    	    	}
    	    	//find the index of two numbers
    	    	int[] res = new int[2];
    	    	for(int i = 0; i < nums.length; i++){
    	    		if(nums[i] == a){
    	    			res[0] = i;
    	    			break;
    	    		}
    	    	}
    	    	if(a != b){
    	    		for(int i = 0; i < nums.length; i++){
    		    		if(nums[i] == b){
    		    			res[1] = i;
    		    			break;
    		    		}
    		    	}
    	    	} else{
    	    		for(int i = 0; i < nums.length; i++){
    		    		if(nums[i] == b && i != res[0]){
    		    			res[1] = i;
    		    			break;
    		    		}
    		    	}
    	    	}
    	    	
    	    	return res;
    	    }
    

  • -5
    Y

    public int[] twoSum_n2(int[] nums, int target) {
    if(nums == null)
    return null;
    int[] nums2 = Arrays.copyOf(nums, nums.length);
    Arrays.sort(nums2);
    int a = 0, b = 0;
    int start = 0, end = nums2.length-1;
    //find two nums
    while(start<end){
    int sum = nums2[start] + nums2[end];
    if(sum < target)
    start++;
    else if(sum > target)
    end--;
    else{
    a = start; b = end;
    break;
    }
    }
    //find the index of two numbers
    int[] res = new int[2];
    res[0] = a;
    res[1] = b;
    return res;
    }


  • 0
    7

    If the nums2={1,2,6,7,8} and the target number is 8, it will give[0,3] only. however we know that the [1,2] is also right answer.

    this method is not easy to output all the results which meet the condition. my idea is to search (target-nums[i]) and you could use binary search to get them.


  • 0
    Y

    Thanks for applying a good solution about outpuing all answers, and yours solution is O(nlogn).
    Moreover, we can change the above algorithm, remove the "break", and continue to all nums, and find all answers.


  • 1
    D

    But the problem says:You may assume that each input would have exactly one solution.


  • 2
    Z

    If you loop backward to find b then you do not have to consider a==b
    for(int i=nums.length-1;i>=0;i--){
    if(nums[i]==b){
    res[1]=i;
    break;
    }
    }


  • 0
    H
    This post is deleted!

  • 0
    H
    This post is deleted!

  • 0
    H
    This post is deleted!

  • 0
    H

    public int[] twoSum(int[] nums, int target) {
    //value -- index.
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    int[] result = new int[2];

        for(int i=0; i < nums.length;i++){
            if(map.containsKey(nums[i])){//already exist;
                if(target == 2*nums[i]){
                    result[0] = map.get(nums[i]);
                    result[1] = i;
                    return result;
                }
                continue;
            }else{
                map.put(nums[i],i);
            }
        }
        
        for(int j=0; j < nums.length; j++){
            if(map.containsKey(target - nums[j])){
                    int index = map.get(target - nums[j]);
                    if(index !=j){
                        result[0] = j;
                        result[1] = index;
                        return result;
                    }
            }
        }
        return result;
    }

  • 0
    G

    @yangliguang your code is awesome,but I have a question.why zhe similar code cost more time in cpp?
    could java efficient than cpp or c?


  • 0
    J

    Can someone explain how a sorting algorithm can run faster than the O(n) time algorithm in the example?


  • 0
    D

    What about below solution.

    public class Solution {
        public int[] twoSum(int[] nums, int target) {
            int[] result= new int[2];
            for (int i=0; i< nums.length; i++){
                for(int j = i+1; j< nums.length; j++){
                    int val = nums[i] + nums[j];
                    if ( val== target){
                        result[0]=i;
                        result[1]=j;
                       break;
                    }
                }
            }
            return result;
        }
    }
    

  • 0
    P
    if(sum < target)
        start++;
    else if(sum > target)
        end--;
    

    This is awesome!


  • 0
    T

    I use the same idea. But it doesn't need to search for the index again. However, comparing Integers is much slower.

    public int[] twoSum(int[] nums, int target) {
            int[] ret = new int[2];        
            int len = nums.length;
            Integer[] index = new Integer[len];
            for(int i=0;i<len;i++)index[i]=i;        
            Arrays.sort(index,new Comparator<Integer>(){
    			public int compare(Integer x,Integer y){
    				return nums[x]-nums[y];
    			}
    		});
            int head = 0,tail = len-1;
            while(tail>head){
            	if(nums[index[head]]+nums[index[tail]]==target){
            		ret[0]=index[head];
            		ret[1]=index[tail];
            		break;
            	}else if(nums[index[head]]+nums[index[tail]]>target){
            		tail--;
            	}else{
            		head++;
            	}
            }
            return ret;
        }
    

  • 0
    P

    @tianye0032 I use c# rewrite the author's idea, but it doesn't like the what the author said that it is more faster than O(n) algorithm. It took 500ms and O(n) took 496ms.I think we have the same situation, O(n) is truly a little bit faster than the O(nlgn) (sorry about my poor English I wish you can understand what I say).


  • 0
    F

    Started from two sides to restore the indexes. Saved some code.

    public class Solution {
        public int[] twoSum(int[] nums, int target) {
            int[] copyNums = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copyNums);
            int left = 0, right = copyNums.length - 1;
            int[] indices = new int[2];
            while (left < right) {
                int sum = copyNums[left] + copyNums[right];
                if (sum == target) {
                    indices[0] = left;
                    indices[1] = right;
                    break;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (copyNums[indices[0]] == nums[i]) {
                    indices[0] = i;
                    break;
                }
            }
            
            for (int i = nums.length - 1; i >= 0; i--) {
                if (copyNums[indices[1]] == nums[i]) {
                    indices[1] = i;
                    break;
                }
            }
            
            return indices;
        }
    }
    

  • 0

    I think step3 is not necessary.

    public int[] twoSum(int[] nums, int target) {
            if(nums == null || nums.length < 2){
                return null;
            }
            NumAndOrder[] numAndOrders = new NumAndOrder[nums.length];
            for(int i = 0 ; i < nums.length; i++){
                numAndOrders[i] = new NumAndOrder(nums[i],i);
            }
            Arrays.sort(numAndOrders);
            int[] result = new int[2];
            int i = 0;
            int j = numAndOrders.length - 1;
            while(i < j){
                if(numAndOrders[i].num + numAndOrders[j].num == target){
                    result[0] = numAndOrders[i].order;
                    result[1] = numAndOrders[j].order;
                    return result;
                } else if(numAndOrders[i].num + numAndOrders[j].num > target ){
                    j--;
                }else{
                    i++;
                }
            }
    
            if(i >= j){
                return null;
            }
            return result;
        }
    
        private static class NumAndOrder implements Comparable<NumAndOrder>{
            public NumAndOrder(int num,int order){
                this.num = num;
                this.order = order;
            }
            int num;
            int order;
            @Override
            public int compareTo(NumAndOrder o) {
                return this.num - o.num;
            }
        }
    

  • 0
    S

    I have a question about how O(NLogN) is more time efficient than O(N)? I mean if N =10000, the LogN factor comes out to be 4 and the O(N) will be four times faster than O(NLogN).
    I tried searching online but couldn't find a clear answer. Any links or help will be appreciated.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.