two_sum_ii_input_array_is_sorted
1from bisect import bisect_right 2 3 4# @leet start 5class Solution: 6 def twoSum(self, numbers: list[int], target: int) -> list[int]: 7 """ 8 This question asks to find the two numbers in an array which sum to target 9 As well, there are two changes: the array is sorted, and you must do this with 10 $O(1)$ extra space. 11 12 To do so, we have to binary search in the array. 13 We can do this with a bisect_left or bisect_right, but keeping in mind that 14 bisect left and bisect right return the insertion point in the array. 15 In bisect_left's case, its the point where insertion would be before any other 16 duplicates, and for bisect_right, it's the pointer where insertion would be after 17 any other duplicates, rather than the actual location in the array. 18 19 So, using bisect_right and checking the position before is easier, since this always give us 20 the last item in the array, so a duplicate like nums = [0, 0], target = 0 21 returns the last item in the array. 22 23 One optimization exists: since we've already passed all items before while 24 iterating, we can check the bisection starting at the next index. 25 This would speed up the algorithm a bit but makes calculating the index to return 26 a bit more cumbersome. 27 """ 28 for i, num in enumerate(numbers): 29 res = bisect_right(numbers, target - num) 30 if numbers[res - 1] == target - num: 31 return [i + 1, res] 32 return [-1, -1] 33 34 35# @leet end 36 37 38def test(): 39 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def twoSum(self, numbers: list[int], target: int) -> list[int]: 8 """ 9 This question asks to find the two numbers in an array which sum to target 10 As well, there are two changes: the array is sorted, and you must do this with 11 $O(1)$ extra space. 12 13 To do so, we have to binary search in the array. 14 We can do this with a bisect_left or bisect_right, but keeping in mind that 15 bisect left and bisect right return the insertion point in the array. 16 In bisect_left's case, its the point where insertion would be before any other 17 duplicates, and for bisect_right, it's the pointer where insertion would be after 18 any other duplicates, rather than the actual location in the array. 19 20 So, using bisect_right and checking the position before is easier, since this always give us 21 the last item in the array, so a duplicate like nums = [0, 0], target = 0 22 returns the last item in the array. 23 24 One optimization exists: since we've already passed all items before while 25 iterating, we can check the bisection starting at the next index. 26 This would speed up the algorithm a bit but makes calculating the index to return 27 a bit more cumbersome. 28 """ 29 for i, num in enumerate(numbers): 30 res = bisect_right(numbers, target - num) 31 if numbers[res - 1] == target - num: 32 return [i + 1, res] 33 return [-1, -1]
def
twoSum(self, numbers: list[int], target: int) -> list[int]:
7 def twoSum(self, numbers: list[int], target: int) -> list[int]: 8 """ 9 This question asks to find the two numbers in an array which sum to target 10 As well, there are two changes: the array is sorted, and you must do this with 11 $O(1)$ extra space. 12 13 To do so, we have to binary search in the array. 14 We can do this with a bisect_left or bisect_right, but keeping in mind that 15 bisect left and bisect right return the insertion point in the array. 16 In bisect_left's case, its the point where insertion would be before any other 17 duplicates, and for bisect_right, it's the pointer where insertion would be after 18 any other duplicates, rather than the actual location in the array. 19 20 So, using bisect_right and checking the position before is easier, since this always give us 21 the last item in the array, so a duplicate like nums = [0, 0], target = 0 22 returns the last item in the array. 23 24 One optimization exists: since we've already passed all items before while 25 iterating, we can check the bisection starting at the next index. 26 This would speed up the algorithm a bit but makes calculating the index to return 27 a bit more cumbersome. 28 """ 29 for i, num in enumerate(numbers): 30 res = bisect_right(numbers, target - num) 31 if numbers[res - 1] == target - num: 32 return [i + 1, res] 33 return [-1, -1]
This question asks to find the two numbers in an array which sum to target As well, there are two changes: the array is sorted, and you must do this with $O(1)$ extra space.
To do so, we have to binary search in the array. We can do this with a bisect_left or bisect_right, but keeping in mind that bisect left and bisect right return the insertion point in the array. In bisect_left's case, its the point where insertion would be before any other duplicates, and for bisect_right, it's the pointer where insertion would be after any other duplicates, rather than the actual location in the array.
So, using bisect_right and checking the position before is easier, since this always give us the last item in the array, so a duplicate like nums = [0, 0], target = 0 returns the last item in the array.
One optimization exists: since we've already passed all items before while iterating, we can check the bisection starting at the next index. This would speed up the algorithm a bit but makes calculating the index to return a bit more cumbersome.
def
test():