Two Sum II
- 1 min read
- LC-Medium
- Two Pointers
3 years ago
sum-ii-input-array-is-sorted/
Solution
- Start out with two pointers, left and right, which start at the outer bounds of the array.
- Add them up. Since the array is sorted, we just have to check the value and move one of the bounds at a time
- I.e. take the first example. First iteration, our sum would be 2 + 15 = 17. 17 is greater than our target, so we need to get to a lower sum. How would we do that? By moving the right pointer so that in our next iteration our sum becomes smaller.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers) - 1
while True:
sum_ = numbers[l] + numbers[r]
if sum_ < target:
l += 1
elif sum_ > target:
r -= 1
else:
return [l + 1, r + 1]