A Java solution without HashMap


  • 3
    C

    I don't think HashMap is necessary for this problem. Just backup and sort the array, then scan it from both sides until the sum meets target. Finally, search the index of the two parts of the sum separately in the backup array.

    public class Solution {
        public int[] twoSum(int[] numbers, int target) {
            if(numbers.length<=1) return null;
            ArrayList<Integer> backup = new ArrayList<Integer>();
            for(int number: numbers) al.add(number);
            Arrays.sort(numbers);
            int[] ret = new int[2];
            int head = 0;
            int tail = numbers.length-1;
            while(head<tail)
            {
                if(numbers[head]+numbers[tail]==target)
                {
                    ret[0] = backup.indexOf(numbers[head])+1;
                    ret[1] = backup.lastIndexOf(numbers[tail])+1;
                    Arrays.sort(ret);
                    return ret;
                }
                if(numbers[head]+numbers[tail]<target) head++;
                else tail--;
            }
            return null;
        }
    }

  • 2
    D

    Sorting the array takes O(nlogn) time. Therefore you need hashMap/hashSet to get O(n) time.


  • 0
    A

    Actually, we can use quick sort here to reduce the sorting time.


  • 0
    W

    I tried quick sort, for sorted array, the time complexity is O(n^2); you need to use merge sort or heap sort to get a guaranteed o(nlgn)


Log in to reply
 

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