题解 | #两数之和#

题目：两数之和

描述：给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

数据范围：2≤len(numbers)≤1500，−10≤numbers≤10^9,0≤target≤10^9

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

例如： 给出的数组为 [20, 70, 110, 150] , 目标值为90

返回一个数组 [1,2] ，因为 numbers_1+numbers_2=20+70=90

思路：这个题目比较麻烦的是时间复杂度要O(nlogn)，简单的代码直接用for循环套for循环，挨个遍历，最后时间复杂度为n(n-1),空间复杂度为1，一开始每思路，但是既然是数组，又有logn，第一个想到的就是二分，而二分是得数组有序，所以我就先排序，然后再二分。排序用另一个数组存，排序的过程是取出一个数，然后用二分和存入的数组比较，确定插入位置，存入数组的为数组下标。分了2-3个数组，一个存大于sum/2，另一个存小于sum/2，还有一个存等于sum/2的，之后计算和，用小于sum/2的数组中的数和大于sum/2的数组中的数求和，用二分的方式去遍历。可以稍微优化一下，用两个数组中长度较短的去二分查找另一个长度较长的数组。

我一开始还想在插入数据的时候顺便去遍历，好像也可以，比较后，如果大于sum/2，就去遍历小于sum/2的数组，不用担心有遗漏，因为如果结果为[A,B]，而A先进入数组，去遍历的时候没有找到B，但是后来B进数组的时候，一定可以找到A。我去写代码，一会再来更新。

已添加了解法二

```#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @param target int整型 
# @return int整型一维数组
#
class Solution:
    @staticmethod
    def saveIn(i,numbers,r):
        mi = 0
        ma = len(r)
        middle = int((ma+mi)/2)
        while(ma > mi):
            middle = int((ma+mi)/2)
            if numbers[i] > numbers[r[middle]]:
                mi = middle+1
            elif numbers[i] < numbers[r[middle]]:
                ma = middle-1
            else:
                mi = middle
                break
        if mi == len(r):
            r.append(i)
        elif numbers[i] < numbers[r[mi]]:
            r.insert(mi,i)
        elif (mi+1)==len(r):
            r.append(i)
        else:
            r.insert(mi+1,i)
            
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        smaller = []
        bigger = []
        middle = int(target/2)
        r = []
        ri = -1
        for i in range(len(numbers)):
            if numbers[i] < middle:
                self.saveIn(i,numbers,smaller)
            elif numbers[i] > middle:
                self.saveIn(i,numbers,bigger)
            else:
                r.append(i+1)
        if len(r) == 2:
            return r
        for j in smaller:
            ma = len(bigger)-1
            mi = 0
            middle = int((ma+mi)/2)
            while ma > mi:
                middle = int((ma+mi)/2)
                if numbers[j] + numbers[bigger[middle]] == target:
                    ri = middle
                    break
                elif numbers[j] + numbers[bigger[middle]] < target:
                    mi = middle + 1
                else:
                    ma = middle -1
            if (numbers[j] + numbers[bigger[mi]]) == target:
                ri = mi
            elif (numbers[j] + numbers[bigger[ma]]) == target:
                ri = ma
            elif numbers[j] + numbers[bigger[middle]] == target:
                ri = middle
            if ri > -1:
                if bigger[ri] > j:
                    r = [j+1,bigger[ri]+1]
                else:
                    r = [bigger[ri]+1,j+1]
                return r



# 解法二
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @param target int整型 
# @return int整型一维数组
#
class Solution:
    @staticmethod
    def saveIn(i,numbers,r):
        mi = 0
        ma = len(r)
        middle = int((ma+mi)/2)
        while(ma > mi):
            middle = int((ma+mi)/2)
            if numbers[i] > numbers[r[middle]]:
                mi = middle+1
            elif numbers[i] < numbers[r[middle]]:
                ma = middle-1
            else:
                mi = middle
                break
        if mi == len(r):
            r.append(i)
        elif numbers[i] < numbers[r[mi]]:
            r.insert(mi,i)
        elif (mi+1)==len(r):
            r.append(i)
        else:
            r.insert(mi+1,i)
    @staticmethod
    def compa(numbers,target,j,arr):
        if len(arr) == 0:
            return []
        ma = len(arr)-1
        mi = 0
        middle = int((ma+mi)/2)
        ri = -1
        while ma > mi:
            if numbers[j] + numbers[arr[middle]] == target:
                ri = middle
                break
            elif numbers[j] + numbers[arr[middle]] < target:
                mi = middle + 1
            else:
                ma = middle -1
            middle = int((ma+mi)/2)
        if (numbers[j] + numbers[arr[mi]]) == target:
            ri = mi
        elif (numbers[j] + numbers[arr[ma]]) == target:
            ri = ma
        elif numbers[j] + numbers[arr[middle]] == target:
            ri = middle
        if ri > -1:
            if ri < j:
                return [arr[ri]+1,j+1]
            else:
                return [j+1,arr[ri]+1]
        return []
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        smaller = []
        bigger = []
        middle = int(target/2)
        r = []
        r_mid = []
        ri = -1
        for i in range(len(numbers)):
            if numbers[i] < middle:
                r = self.compa(numbers,target,i,bigger)
                if len(r) == 2:
                    return r
                self.saveIn(i,numbers,smaller)
            elif numbers[i] > middle:
                r = self.compa(numbers,target,i,smaller)
                if len(r) == 2:
                    return r
                self.saveIn(i,numbers,bigger)
            else:
                r_mid.append(i+1)
        if len(r_mid) == 2:
            return r_mid