题目一：和为 s 的两个数字
题目描述：
输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40 输出：[10,30] 或者 [30,10]
限制：
1 <= nums.length <= 10^5 1 <= nums[i] <= 10^6
解题思想
遇题不会想暴力算法，先来看看直观的解题思路：
- 暴力法
首先选择数组一个数字，挨个从剩下的 n-1 个数字找两数之和是不是等于 s。
def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return nums[i], nums[j] return []
很容易看到，用到了双层循环，所以时间复杂度: O(n2)
LeetCode 提交超时：26 / 36 个通过测试用例
- 哈希表
上面的代码用了两成循环，其实转化一下思想，能不能只用一个 for 循环呢？
方法：TwoSum 那道题
作为一个 Pythoner，怎么会轻言放弃，办法是一定的。list 不好使，那我们还有 set 呢。也就是哈希表法：利用一次遍历，先找一个数，然后依次遍历查看 target-i 是否在这个 set 中，如果在，即返回。
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: li_set = set(nums) for i in li_set: if (target - i) in li_set: return i, target - i return []
时间复杂度: O(n)，只使用了一次 for 遍历数组
空间复杂度: O(n)，此方法利用了一个 set
- 双指针
就像小时候的数学刷题一样，所有的题目条件一定是最关键的，我们能够看到，还有一个很题目中关键的信息没有用到：递增数组。
做出了上面的方法后，发现其实哈希表法并没有利用题目中给出递增排序数组的特点。利用递增的特点找到空间复杂度 O(1)的解题方法--双指针对撞：
取两端
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: rPointer, lPointer = 0, len(nums) - 1 while rPointer < lPointer: twoSum = nums[rPointer] + nums[lPointer] if twoSum == target: return nums[rPointer], nums[lPointer] elif twoSum > target: lPointer -= 1 else: rPointer += 1 return []
- 别忘了二分查找啊
“递增+有序”，难道二分查找不配有名字吗？
采用二分查找法缩小双指针遍历范围：left 和 right 分别记录当前查找数组范围的最小元素下标和最大元素下标，mid=(R-L)//2+L 为中间下标；
若 nums[mid]+nums[left]>target ，则 mid 下标元素及其右边任何元素两两之和均大于 target ，只可能在 mid 左边取得，故 right=mid-1 ；
若 nums[mid]+nums[right]<target ，则 mid 下标元素及其左边任何元素两两之和均小于 target，只可能在 mid 右边取得，故 left=mid+1；
若 nums[mid]+nums[left]<=target<=nums[mid]+nums[right] 或者 left>=right 时,则结束二分查找；
若以 left>=right 结束循环，则数组中不存在和为 s 的两个元素，返回空数组。
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: n=len(nums) L,R=0,n-1 res=[] mid=(R-L)//2+L while L<R: if nums[L]+nums[R]>target: if nums[L]+nums[mid]>target: R=mid-1 mid=(R-L)//2+L elif nums[L]+nums[mid]==target: res.extend([nums[L],nums[mid]]) break else: R-=1 mid=(R-L)//2+L elif nums[L]+nums[R]==target: res.extend([nums[L],nums[R]]) break else: if nums[R]+nums[mid]>target: L+=1 mid=(R-L)//2+L elif nums[R]+nums[mid]==target: res.extend([nums[mid],nums[R]]) break else: L=mid+1 mid=(R-L)//2+L return res
