2 Sum In A Sorted Array Problem

Given an array in increasing order and a target, return indices of two numbers such that they add up to the target. You have to return an array of indices where the zeroeth index value is less than first index value.

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: 
nums = [2, 7, 18, 15], target = 20 
nums = [3,3], target = 6
Explanation:
The sum of 2 and 18 is 20. Therefore index1 = 1, index2 = 3.
The sum of 3 and 3 is 6. Therefore index1  = 0, index2 = 1. 

Approach-1: Brute Force
We use two loops and check whether the sum is equal to the target. Time complexity of this approach is O(n^2).

Implementation in Java:

public class TargetSum {

    public static void main(String[] args)
    {
        // driver code

        int[] nums = { 2, 7, 11, 15 };
        int target = 9;
        int ans[] = targetSum(nums, target);
        System.out.println("[" + ans[0] + ", " + ans[1] + "]");
    }

    public static int[] targetSum(int[] a, int target)
    {
       int[] ans = new int[2];
        for(int i = 1 ; i<=a.length ; i++){
            for(int j = i+1 ; j<=a.length ; j++){
                if(a[i-1]+a[j-1] == target){
                    ans[0] = i;
                    ans[1] = j;
                    break;
                }
            }
        }
        
        return  ans;
    
    }
}

Output:

[1, 2] 

Approach-2: Two pointer Approach
We keep a pointer to the first element of the array and a pointer to last element and calculate their sum.
If sum is equal to the target then we store the indices int the ans array, if sum is greater we shift the pointer to left(pointer pointing to last element) and if the sum is smaller we shift the pointer towards right(the pointer pointing to first element). Time complexity of this approach is O(n).

Implementation in Java:

public class TwoSum {

    public static void main(String[] args)
    {
        // driver code

        int[] nums = { 2, 7, 11, 15 };
        int target = 9;
        int ans[] = targetSum(nums, target);
        System.out.println("[" + ans[0] + ", " + ans[1] + "]");
    }

    public static int[] targetSum(int[] a, int target)
    {
       int[] ans = new int[2];
        int i = 1;
        int j = a.length;
        
        while(i<j){
            int sum = a[i-1] + a[j-1];
            
            if(sum>target){
                j--;
            }
            else if(sum<target){
                i++;
            }else{
                ans[0]  = i;
                ans[1] = j;
                break;
            }
        }
        
        return ans;
    
    }
}

Output:

[1, 2]