Java, 2 solution, O(nlgn) time and O(1) space using sort and binarysearch, O(n) time and O(n) space using hash


  • 0
    S

    Solution 1, Sort and binary search, costs O(n) time and O(n) space using hash.

    import java.util.Arrays;

    public class SortSearchSolution {
    	public int[] twoSum(int[] numbers, int target) {
    		int start = 0, end = 0, temp;
    		int[] back = Arrays.copyOf(numbers, numbers.length);
    		int[] reslut = new int[] { 0, 0 };
    		Arrays.sort(back);
    		for (int i = 0; i < back.length; i++) {
    			start = Arrays.binarySearch(back, target - back[i]);
    			if (start > 0 && start != i) {
    				start = back[start];
    				end = back[i];
    				break;
    			}
    		}
    		for (int i = 0; i < numbers.length; i++)
    			if (numbers[i] == start) {
    				reslut[0] = i + 1;
    				break;
    			}
    		for(int i=0;i<numbers.length;i++)
    			if(numbers[i]==end&&i!=reslut[0]-1){
    				reslut[1]=i+1;
    				break;
    			}
    		if (reslut[0] > reslut[1]) {
    			temp = reslut[0];
    			reslut[0] = reslut[1];
    			reslut[1] = temp;
    		}
    		return reslut;
    	}
    }
    

    Solution 2, HashMap, costs O(n) time and O(n) space.

    import java.util.HashMap;
    import java.util.Map;
    
    public class Solution {
    	public int[] twoSum(int[] numbers, int target) {
    		Map<Integer, Integer> map=new HashMap<>(numbers.length*2);
    		for(int i=0;i<numbers.length;i++){
    			Integer company=map.get(target-numbers[i]);
    			if(company==null)
    				map.put(numbers[i], i);
    			else
    				return new int[]{company+1,i+1};
    		}
    		return null;
    	}
    }
    

    But this two method do not have that much different in running as it should be. Method 1 costs me 220 ms, and method 2 costs me 241 ms.


Log in to reply
 

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