题解 | #两数之和#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param numbers int整型一维数组
# @param target int整型
# @return int整型一维数组
#
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # refactor and sort the list
        sorted_numbers = [(idx, val) for idx, val in enumerate(numbers)]
        sorted_numbers.sort(key=lambda x: x[1])

        # find the cutpoint
        s = 0
        idx_1, idx_2 = 0, 1
        for i in range(len(sorted_numbers) - 1):
            s = sorted_numbers[i][1] + sorted_numbers[i + 1][1]
            if s >= target:
                idx_1, idx_2 = i, i + 1
                break

        # search bi-directional
        while True:
            s = sorted_numbers[idx_1][1] + sorted_numbers[idx_2][1]
            if s == target:
                break
            elif s > target:
                idx_1 -= 1
            else:
                idx_2 += 1

        # return the result
        res = [sorted_numbers[idx_1][0] + 1, sorted_numbers[idx_2][0] + 1]
        res.sort()
        return res