两数之和 VII

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

描述

给定一个已经按绝对值升序排列的数组，找到两个数使他们加起来的和等于特定数。

函数应该返回这两个数的下标，index1必须小于index2。注意：数组的下标以0开始。

你不能对该数组进行排序。

---

• 数据保证$numsnums$中的所有数的互不相同的。

• $numsnums$数组长度$≤100 000≤100000$

• $numsnums$内的数$≤109≤109$

样例

输入: [0,-1,2,-3,4]1输出: [[1,2],[3,4]]说明: nums[1] + nums[2] = -1 + 2 = 1, nums[3] + nums[4] = -3 + 4 = 1你也可以返回 [[3,4],[1,2]]，系统将自动帮你排序成 [[1,2],[3,4]]。但是[[2,1],[3,4]]是不合法的。

挑战

$O(n)O(n)$的时间复杂度和$O(1)O(1)$的额外空间复杂度

分析：

正常2sum, 期待数：当前Index，用hashmap/dict做会很简单，传统2sum 加一句 if abs(target - nums[i]) < abs(nums[i]): 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 = {}
        res = []
        if len(nums) < 2:
            return res
        for i, num in enumerate(nums):
            if num in find:
                res.append([find[num], i])
            if abs(target - num) < abs(num):
                continue
            find[target - num] = i
        return res
                


```