O(n^2) is too slow


  • 0
    S

    O(n^2) solution is the simplest solution for this but complains about the running time. I used HashMap so that it maintains O(n) for average cases.


  • 0
    S
    1. Basically put all numbers in a HashMap (key: numbers, values: indices)
    2. Loop through every HashMap element and check if target minus key value exists

    Here is my accepted code:

    public class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int length = numbers.length;
            int [] output = {-1, -1};
            HashMap <Integer, ArrayList<Integer>> hm = new HashMap <Integer, ArrayList<Integer>>();
            for (int i = 0; i < length; i++) {
                if (!hm.containsKey(numbers[i])) {
                    ArrayList<Integer> al = new ArrayList<Integer>();
                    al.add(i+1);
                    hm.put(numbers[i], al);
                }
                else {
                    int key = numbers[i];
                    hm.get(key).add(i+1);
                }
            }
            for (int key : hm.keySet()) {
                ArrayList<Integer> al = hm.get(key);
                int num1 = al.get(0);
                
                if (hm.containsKey(target - key)) {
                    if (hm.get(target-key).size() > 0) {
                        al.remove(0);
                        output[0] = num1;
                        output[1] = hm.get(target-key).get(0);
                        Arrays.sort(output);
                        return output;
                    }
                }
            }
            return output;
        }
    }

  • 0
    H

    if numbers is {3, 2, 5, 9, 9, 7}, you will error。You need to make a little change.like that:

    public int[] twoSum2(int[] numbers, int target) {
    	int length = numbers.length;
    	int[] output = { -1, -1 };
    	HashMap<Integer, ArrayList<Integer>> hm = new HashMap<Integer,ArrayList<Integer>>();
    	for (int i = 0; i < length; i++) {
    		if (!hm.containsKey(numbers[i])) {
    			ArrayList<Integer> al = new ArrayList<Integer>();
    			al.add(i + 1);
    			hm.put(numbers[i], al);
    		} else {
    			int key = numbers[i];
    			hm.get(key).add(i + 1);
    		}
    	}
    	for (int key : hm.keySet()) {
    		ArrayList<Integer> al = hm.get(key);
    		int num1 = al.get(0);
    
    		if (hm.containsKey(target - key)) {
    			if (target - key == key && al.size() > 1) {
    				al.remove(0);
    				output[0] = num1;
    				output[1] = hm.get(target - key).get(0);
    				Arrays.sort(output);
    				return output;
    			} else if (target - key != key) {
    				output[0] = num1;
    				output[1] = hm.get(target - key).get(0);
    				Arrays.sort(output);
    				return output;
    			}
    		}
    	}
    	return output;
    }

Log in to reply
 

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