Since there's only constant space we can use, we won't take set for searching the num target.
instead, we will use the two pointer technique, each point to the head and tail, when the sum of the two pointer values is bigger than target, move the right pointer to the prev element, else move left pointer to the next index.
This approach will ensure to find and converge all the possible combinations.
time: O(N) -> N is length of nums
space: O(1) -> two int
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers) - 1
while l < r:
cur_sum = numbers[l] + numbers[r]
if cur_sum == target:
return [l + 1, r + 1]
if cur_sum > target:
r -= 1
else:
l += 1
return []
Since there's only constant space we can use, we won't take set for searching the num target. instead, we will use the two pointer technique, each point to the head and tail, when the sum of the two pointer values is bigger than target, move the right pointer to the prev element, else move left pointer to the next index.
This approach will ensure to find and converge all the possible combinations.
time: O(N) -> N is length of nums space: O(1) -> two int