剑指offer57:和为s的两个数字 python
题目描述解法
题目描述
解法
双指针 由于是递增数列，所以两个指针分别放在头尾。如果和大于target那么尾指针往左移一位，反之，头指针右移一位。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
i, j = 0, len(nums)-1
while i != j:
if nums[i] + nums[j] < target:
i += 1
if nums[i] + nums[j] > target:
j -= 1
if nums[i] + nums[j] == target:
return [nums[i],nums[j]]
return None
双指针+2分法 可以增加一个2分判断是否需要加速指针缩进。 a 首先初始化两个指针，头指针i和尾指针j，split =(i+j)/2。 b 如果nums[i]+nums[j] < target，判断nums[split]+nums[i]，如果小于，那么不需要加速缩进，说明结果在split和j之间，反之，则加速缩进，说明最终结果在i和split之间，若等于，那么直接return。 c 如果nums[i]+nums[j] < target，同上。 d 如果等于，return nums[i]和nums[j]
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
i, j = 0, len(nums)-1
while i != j:
if nums[i] + nums[j] < target:
split_idx = int((i+j)/2)
if nums[split_idx] + nums[j] < target:
i = split_idx + 1
elif nums[split_idx] + nums[j] > target:
i += 1
else:
return [nums[split_idx],nums[j]]
elif nums[i] + nums[j] > target:
split_idx = int((i+j)/2)
if nums[split_idx] + nums[i] > target:
j = split_idx - 1
elif nums[split_idx] + nums[i] < target:
j -= 1
else:
return [nums[split_idx],nums[i]]
else:
return [nums[i],nums[j]]
return None
