Share my java AC solution.


  • 99
    T

    Without HashMap, just have two pointers, A points to index 0, B points to index len - 1, shrink the scope based on the value and target comparison.

    public int[] twoSum(int[] num, int target) {
        int[] indice = new int[2];
        if (num == null || num.length < 2) return indice;
        int left = 0, right = num.length - 1;
        while (left < right) {
            int v = num[left] + num[right];
            if (v == target) {
                indice[0] = left + 1;
                indice[1] = right + 1;
                break;
            } else if (v > target) {
                right --;
            } else {
                left ++;
            }
        }
        return indice;
    }

  • 0
    R
    This post is deleted!

  • 34
    D

    The code is clean and elegant, but I would change one line:

    long v = num[left] + num[right];
    

    in case of the integer overflow.


  • 0
    A

    great solution. i know it works, but am struggling to understand why; feel like magic. can you explain a little bit.


  • 0
    S

    Great solution, but could you explain a bit how it's utilizing its already SORTED attribute?


  • -1
    G

    Since the array is sorted, we can leverage it by using binary search which is O(logn) instead of a HashMap solution which is O(n) . So the code is simple and self explanatory for most of the part. It is noting but Binary search as we already have a sorted array


  • 9
    M

    Can I ask why the big O here is O(log n)? Actually, what happen here is not binary search. It just use two pointers and worst case could be O(n).


  • 0
    H

    I think its still O(n) because the number of element you have to check is still proportional to the length of given int array.


  • 0
    M

    what's the time complexity of this two pointers solution? O(logN)?


  • 18
    V

    nicer and shorter!

    public int[] twoSum(int[] numbers, int target) {
            int start = 0, end = numbers.length - 1;
            while(start < end){
                if(numbers[start] + numbers[end] == target) break;
                if(numbers[start] + numbers[end] < target) start++;
                else end--;
            }
            return new int[]{start + 1, end + 1};
        }

  • 1
    Y

    O(n), no binary reducing search place here


  • 0
    O

    shorter

    public int[] twoSum(int[] numbers, int target) {
            for (int i = 0, n = numbers.length; i < n - 1; i++) {
                int j = Arrays.binarySearch(numbers, i + 1, n, target - numbers[i]);
                if (j > 0) return new int[]{i + 1, j + 1};
            }
            return null;
        }

  • 0
    C

    @ofLucas
    this is n(logn) right?:clap:


  • 1
    S

    Seems not a O(logn) solution. The key point of binary search which can bring you O(logN) is divide the space by two. Which means something like right = mid or left = mid. But the code here is simply incrementing and decrementing. I would say it's a O(n) solution.


  • 0
    A

    Could someone explain why the indice[0] is left + 1 instead of just left? If we found the correct sum at index of left and right why do we increment each by 1?


  • 1

    @vimukthi But the run time of your program is 2ms, which is slower. I don't know why, can anybody who explain?


  • 0
    J

    @aoben10 this is required by this problem. You can read it from the description. The index starts from 1, instead of 0.


  • 0
    H
    This post is deleted!

  • 1
    H

    @Harrywithcode Time Limit Exceeded might be occurred when n is a big data and the target i, j is in the center of the array.
    For example,
    [0,0,0,0,...,0,2,3,9,9,...,9] target sum is 5


  • 0

    I logged in just to upvote your solution. Good job PO!


Log in to reply
 

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