Java solution using two pointers


  • 1
    K
    /*
        
        Trick : tow sum --> use pointers(it is sorred) --> compare sum left + right  with target not just one side of it
        
        Brain refresh : do not think same as TWO SUM -- > prevent your mind from thinking in another way
        
        */
        public int[] twoSum(int[] numbers, int target) {
            // same number should not use twice
            int left = 0; int right = numbers.length -1;
            while (left < right) {
                int sum = numbers[left] + numbers[right];
                if (sum < target) {
                    left ++;
                }else if (sum > target) {
                    right--;
                }else {
                    return new int[]{left + 1, right +1};
                }
            }
            return new int[2];
        }
    

    In this problem , I first think in TWO SUM ways --> but use binary search instead of map. However, the efficiency is O(nLogn). So I came up with solution using two pointers and sorted array property well.


Log in to reply
 

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