This is my Java code. Is it the best efficient?


  • -1
    E
    public class Solution {
        public int[] twoSum(int[] numbers, int target) {
            
            int check;
            for(int i=0;i<numbers.length;i++) {
                
                for(int j=i+1;j<numbers.length;j++) {
                    check = numbers[i] + numbers[j];
                    if(check == target)
                        return new int[] {i+1, j+1};
                }
            }
            
            return null;
        }
    }

  • 7
    B

    The runtime complexity of your solution is O(n2). Below are a couple of other approaches.

    1. Sort the array. Then for each element numbers[i], binary search if (target -n[i]) exists in the array. O(nlogn) runtime, and O(1) memory
    2. Use a hash table with key = numbers[i], and value = i. Then do a hash lookup instead of binary search. O(n) runtime and O(n) memory.

    Of course, there's details you need to work out when implementing these approaches which I have intentionally left out (so you still have interest in solving this problem).


  • 2
    V

    Time complexity of your algorithm is O(n^2) and Space Complexity is O(n). It can be optimized by using a HashMap. The upper bound of time complexity by using hashMap is O(nlogn) because "get" operation in HashMap has O(1) time complexity in the average case and O(n) time complexity in the worst case. So, depending on the internal implementation of HashMap running time varies. In Java the running time is close to O(n), where as in C++ running time is close to O(nlogn). Please find this Java optimised solution.

    public class Solution{
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; i++) {
            if (hashMap.containsKey(target - numbers[i])) {
                result[1] = i + 1;
                result[0] = hashMap.get(target - numbers[i]);
                return result;
            }
            hashMap.put(numbers[i], i + 1);
        }
        return result;
    }
    }

  • 0
    L

    Sort the array then search is valid for return two sum, but may be hard to return index of chosen number.
    HashTable is fine.


  • 0
    Z

    this is a good point


Log in to reply
 

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