两数之和 VII

给定一个已经按绝对值升序排列的数组，找到两个数使他们加起来的和等于特定数。 函数应该返回这两个数的下标，index1必须小于index2。注意：数组的下标以0开始。 你不能对该数组进行排序。

https://www.lintcode.com/problem/1879/description?utm_source=sc-cheatsheet-cyc

• 数据保证$𝑛𝑢𝑚𝑠nums$中的所有数的互不相同的。

• $𝑛𝑢𝑚𝑠nums$数组长度$≤100 000≤100000$

• $𝑛𝑢𝑚𝑠nums$内的数$≤109≤109$

解题思路

find dict存delta:index (delta = target-current #)

一旦当前数存在find里，证明是要找的

绝对值此处用来判断是否进行下去，如果delta绝对值已经小了，直接continue.

```python
from typing import (
    List,
)

class Solution:
    """
    @param nums: the input array
    @param target: the target number
    @return: return the target pair
             we will sort your return value in output
    """
    def two_sum_v_i_i(self, nums: List[int], target: int) -> List[List[int]]:
        # write your code here
        find = {} # number:index
        res = []
        for i in range(len(nums)):
            if nums[i] in find:
                res.append([find[nums[i]], i])
            if abs(target - nums[i]) < abs(nums[i]):
                continue #当前绝对值已经不可能再大 没必要继续了
            find[target-nums[i]] = i #存的是delta， 不是原本的数，所以找的时候直接用当前数字找。不需要额外target-nums[i]
        return res



```