1. class Solution {
  2.     /** Bruite force, O(N) O(N) */
  3.     public int[] twoSum(int[] nums, int target) {
  4.         int[] arr = new int[]{-1,-1};
  5.  
  6.         Map<Integer, Integer> map = new HashMap<>();
  7.  
  8.         for(int i=0; i <nums.length; i++)
  9.         {
  10.             int diff = target - nums[i];
  11.  
  12.             if(map.containsKey(diff))
  13.             {
  14.                 arr[0] = map.get(diff);
  15.                 arr[1] = i;
  16.                 break;
  17.             }
  18.             else
  19.                 map.put(nums[i], i);
  20.         }
  21.         return arr;
  22.     }
  23.  
  24. 	/** Two pointer approach, O(N) O(1) */
  25.     // works only if array has positive elements
  26.     public int[] twoSum(int[] nums, int target) {
  27.         int i=0;
  28.         int j=nums.length-1;
  29.         int[] arr = new int[]{-1,-1};
  30.  
  31.         while(i < j)
  32.         {
  33.             if(nums[i] + nums[j] == target)
  34.             {
  35.                 arr[0] = i;
  36.                 arr[1] = j;
  37.                 break;
  38.             }
  39.             else if(nums[i] + nums[j] < target)
  40.                 i++;
  41.             else if(nums[i] + nums[j] > target)
  42.                 j--;
  43.         }
  44.         return arr;
  45.     }
  46. }