Solution 1Two Pointer
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0
right = len(numbers)-1
while left < right:
current = numbers[right] + numbers[left]
if current == target:
return [left+1, right+1]
if current > target:
right -= 1
else:
left += 1
return []public int[] twoSumII(int[] numbers, int target) {
/*
* Change function name from twoSumII to twoSum
*/
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int current = numbers[left] + numbers[right];
if (current == target) {
return new int[] { left + 1, right + 1 };
}
if (current > target) {
right--;
} else {
left++;
}
}
return new int[] {};
}Solution 2Binary Search
Classic example of over engineering 😑. Don't follow this!
Python
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
'''
Classic example of over engineering 😑. Don't follow this!
'''
left = 0
right = bisect.bisect_right(numbers, target-numbers[left])-1
while right > left:
need = target - numbers[right]
left = bisect.bisect_left(numbers, need, left, right)
if numbers[left] == need:
return [left+1, right+1]
right = bisect.bisect_right(numbers, target-numbers[left], left, right)-1
return []