167. Two Sum II - Input array is sorted
Description
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.
Constraints
2 <= nums.length <= 3 * 104-1000 <= nums[i] <= 1000numsis sorted in increasing order.-1000 <= target <= 1000
Approach
Links
GeeksforGeeks
YouTube
Examples
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
Input: numbers = [2, 3, 4], target = 6
Output: [1, 3]
Input: numbers = [-1, 0], target = -1
Output: [1, 2]
Solutions
/**
* 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;
}
}Follow up
Last updated
Was this helpful?