Java O(n)t O(1)s


  • 0
    R

    prune some cases
    eg.
    [0,0,0,0,0,0,0,0,0,2,3,4,4,4,4,4,4,4,4,4,4,4,4,4]
    5
    int the above case, we can just skip the same elements 0,4 and jump to [2,3].

    public class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int lo=0;
            int hi=numbers.length-1;
            while(lo<hi){
                if(numbers[lo]+numbers[hi]==target) return new int[]{lo+1,hi+1};
                else if(numbers[lo]+numbers[hi]<target){
                    int a=numbers[lo];
                    while(++lo>numbers.length&&numbers[lo]==a);
                }
                else{
                     int a=numbers[hi];
                    while(--hi>=0&&numbers[hi]==a);
                }
            }
            return new int[]{-1,-1};
        }
    }
    

Log in to reply
 

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