Two Sum II - Input array is sorted

Question

Leetcode #167 is almost same as #1, but why I cannot only add a if condition?

Q: Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.

Example: Input: numbers = [2,7,11,15], target = 9 Output: [1,2]

The sum of 2 and 7 is 9. 
Therefore index1 = 1, index2 = 2.

My code:

class Solution {
public int[] twoSum(int[] numbers, int target) {
        for (int i = 1; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[j] == target - numbers[i]) {
                    if(numbers[i] < numbers[j])
                        return new int[] { i, j };
        }
    }
}
 return null;
}

}

Why I always return null? where is my mistake? How to fix it?

Answer 1

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

Answer 2

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

[question]: 167. Two Sum II - Input array is sorted

Using the two-pointer technique:-

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0)
            return null;
        int i = 0;
        int j = numbers.length - 1;
        while (i < j) {
            int x = numbers[i] + numbers[j];
            if (x < target) {
                ++i;
            } else if (x > target) {
                j--;
            } else {
                return new int[] { i + 1, j + 1 };
            }
        }
        return null;
    }
}

Answer 3

This is a better solution as it's much faster and covers all test cases as well:

class Solution {
public int[] twoSum(int[] numbers, int target) {
    int l = 0, r = numbers.length - 1;
    while (numbers[l] + numbers[r] != target) {
        if (numbers[l] + numbers[r] > target) 
            r--;
        else 
            l++;
        if (r == l) return new int[]{};
    }
    return new int[]{l + 1, r + 1};
  }
}

Answer 4

You are starting first for-loop with i = 0, what you should do is start it with i = 1.

Working code:

public class Solution 
{
    public static void main(String[] args)
    {
        int[] num = {2,7,11,5};
        int n = 13;
        int[] answer = new int[2];
        answer = twoSum(num,n);
        if(answer != null)
            for(int i=0;i<2;i++)
                System.out.printf( answer[i] +" ");
    }


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

Note: I have placed an IF before FOR in main() so that if we find no such integers that adds up to give target integer, it'll not throw a NullPointerException.

Answer 5

I have modified your code and added code comments on why your previous code has errors. Refer to code below for details.

public class Main {

    public static void main(String[] args) {
        int target = 9;
        int[] numbers = new int[] { 2, 7, 11, 15 };
        int[] result = twoSum(numbers, target);
        if (result != null) {
            System.out
                    .println("The sum of " + numbers[result[0]] + " and " + numbers[result[1]] + " is " + target + ".");
            System.out.println("Therefore index1 = " + (result[0] + 1) + ", index2 = " + (result[1] + 1));
        } else {
            System.out.println("No Solution found!");
        }
    }

    public static int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) { // array index starts at 0
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[j] + numbers[i] == target) { // add the current numbers
                    // if (numbers[i] < numbers[j]) // not needed
                    return new int[] { i, j };
                }
            }
        }
        return null;
    }

}

Sample input:

numbers = [2, 7, 11, 15];

Sample output:

The sum of 2 and 7 is 9.
Therefore index1 = 1, index2 = 2

Answer 6

Because the question says array starts from 1 does not mean array starts from 1 in java.If you want to return i,j as non-zero you should go from 1 to length+1 and then inside the conditions you should check indexes as i-1,j-1 or just start from 0 and return i+1,j+1.

class Solution {
  public int[] twoSum(int[] numbers, int target) {
    for (int i = 1; i < numbers.length+1; i++) {
        for (int j = i + 1; j < numbers.length+1; j++) {
            if (numbers[j-1] == target - numbers[i-1]) {
                if(numbers[i-1] < numbers[j-1])
                    return new int[] { i, j };
            }
        }
    }
     return null;
  }
 }

or you can do,

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