LCR 006. 两数之和 II - 输入有序数组

一.题目：

LCR 006. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

二.我的原始解法-暴力解法超时：

class Solution:

    def twoSum(self, numbers: List[int], target: int) -> List[int]:

        # 暴力解法

        result = []

        for i in range(0,len(numbers)):

            for j in range(i+1,len(numbers)):

                if numbers[i] + numbers[j] == target:

                    result.extend([i,j])

                    return result

三.其他人的正确及好的解法，力扣解法参考：

力扣标准解法二分查找和双指针：LCR 006. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

四.对于别人解法的消化及总结：

（1）二分查找解法要注意的是这道题查找的是两个数，查找第一个数的时候需要遍历for循环，查找第二个数的时候是常规的二分查找方法，高低指针，查找的数组范围是第一个数后面到原始数组末尾，随着第一个数的遍历，第二个数的查找范围也在变化，这是和常规二分查找不同的地方。每次for循环遍历第一个数的时候就重新给low，high赋值，由于查找两个数，第一个数时间复杂度n，第二个数是常规的二分复杂度logn，最后是o(n*logn)，这个也需要注意一下，空间复杂度由于除了返回的两个元素的短数组外只用了常量，所以为o(1)

二分查找实现

（2）双指针解法的核心思想是不断缩减查找范围，和二分查找分区域查找思想不同，而是用两个指针互相逼近最终找到目标，这道题要找两个数，最终就是两个指针分别指向这两个目标数字结束。拿low+high和target比较，如果low+high=target，直接返回low,high作为结果，如果low+high<target，由于high是从最大数开始的，只有一种可能就是low小了，就调整low=low+1，如果low+high>target，由于low是从最小数开始的，只有一种可能就是high大了，就调整high=high-1

双指针实现