167. Two Sum II - Input array is sorted
Last updated
Last updated
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public int[] twoSum(int[] numbers, int target) {
Map<Integer, Integer> indexMap = new HashMap();
int[] result = new int[2];
for(int i = 0; i < numbers.length; i++) {
int diff = target - numbers[i];
if(indexMap.containsKey(diff)) {
result[0] = indexMap.get(diff);
result[1] = i+1;
break;
} else {
indexMap.put(numbers[i], i+1);
}
}
return result;
}
}/**
* Time complexity : O(n). Each of the n elements is visited at most once,
* thus the time complexity is O(n).
* Space complexity : O(1). We only use two indexes.
*/
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
int leftPtr = 0, rightPtr = numbers.length-1;
while(leftPtr < rightPtr) {
int sum = numbers[leftPtr]+numbers[rightPtr];
if(sum == target) {
result[0] = leftPtr+1;
result[1] = rightPtr+1;
break;
} else if(sum > target) {
rightPtr--;
} else {
leftPtr++;
}
}
return result;
}
}