when the size of array is big enough, it cheats the compiler even it works well


  • 0

    Here is my answer. Actually the worst time is still O(n), I just do some extra work like 'binary search' when it's not the worst.

    public int[] twoSum(int[] numbers, int target)
    	{
    		int[] a = {0,0};
    		int n = numbers.length;
    		if(n > 1)
    		{
    			int p = 0;
    			int q = n - 1;
    			while(p < q)
    			{
    				if(target - numbers[p] == numbers[q])
    				{
    					a[0] = p + 1;
    					a[1] = q + 1;
    					return a;
    				}
    				else
    					if(target - numbers[p] < numbers[q])
    					{
    						int mid = p + (q - p) / 2;
    						if(target - numbers[p] == numbers[mid])
    						{
    							a[0] = p + 1;
    							a[1] = mid + 1;
    							return a;
    						}
    						else
    							if(target - numbers[p] < numbers[mid])
    								q = mid;
    							else
    								q--;
    					}
    					else
    					{
    						int mid = p + (q - p) / 2;
    						if(target - numbers[mid] == numbers[q])
    						{
    							a[0] = mid + 1;
    							a[1] = q + 1;
    							return a;
    						}
    						else
    							if(target - numbers[mid] > numbers[q])
    								p = mid;
    							else
    								p++;
    					}
    			}
    		}
    		return a;
    	}
    

Log in to reply
 

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