Java O(n) solution ignoring the redundant values


  • 0
    S

    Since we are given a sorted arrays, I am using two flags, 'start' and 'end'.
    The flag 'start' proceeds from the beginning of the array and the flag 'end' moves from the end of the array to the mid point.

    First, ignore the values greater from the target. For this, I am setting 'end' to position where the value is equal to the target or less.

    Before, decrementing the 'end' flag, I will increment the 'start' flag till the sum of the values at start and end is equal or greater than the target. Then 'end' is decremented. This is continued till the required indexes are found.

    public class Solution {
        public int[] twoSum(int[] nums, int target) {
            int[] n = {1,2};
            int start = 0;
            int end = nums.length - 1;
            for(int i = nums.length-1; i > 0;i--){
                if(nums[i]<target){
                    end = i;
                    break;
                }
            }
            for(int i = 0; i < nums.length; i++){
                while(nums[start]+nums[end] <= target){
                    if(nums[start]+nums[end] == target){
                        n[0] = start+1;
                        n[1] = end+1;
                        return n;
                    }
                    start++;
                }
                end--;
            }
            return n;
        }
    }
    

Log in to reply
 

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