LeetCode-高效制胜-两数之和 II - 输入有序数组

yfx

July 27, 2021

1001 views

No comments

1334 words

算法 C/C++ Python

# Problem - [两数之和 II - 输入有序数组](https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/)

## 方法一：双指针

> 本题与[两数之和](https://leetcode-cn.com/problems/two-sum/)同样可以采用哈希表的做法。
>
> 注意到本题多了一个数组为升序的条件，该如何使用呢？
>
> 我们要寻找满足$A[i] + A[j] = target$的`i`与`j`，我们初始时令`i = 0、j = n - 1`(`n`为数组长度)，即取数组搜索范围内当前的最小值与最大值。
>
> 若此时两数之和大于`target`，则需要缩小和因为`A[i]`已经为当前搜索空间最小值故只能进行`-- j`操作。反之则只能操作`++ i`。
>
> 双指针算法在空间复杂度上优于哈希表做法。

### 参考代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-da5505cdf31a45048509cc57d6bd72a8780' role="tab" data-target='#tabs-da5505cdf31a45048509cc57d6bd72a8780'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-5f499915a25122eedfe7fea5b68d409f581' role="tab" data-target='#tabs-5f499915a25122eedfe7fea5b68d409f581'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-da5505cdf31a45048509cc57d6bd72a8780' class="tab-pane fade active in">

```cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) return {l + 1, r + 1};
            else if (sum > target) -- r;
            else ++ l;
        }
        return {-1, -1};
    }
};
```

</div><div role="tabpanel" id='tabs-5f499915a25122eedfe7fea5b68d409f581' class="tab-pane fade  ">

```python
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            sum = numbers[l] + numbers[r]
            if sum == target: return [l + 1, r + 1]
            elif sum > target: r -= 1
            else: l += 1
        return [-1, -1]
```

~~ps：加强python语法的学习！~~

</div>
</div>
</div>

### 复杂度分析：

* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$

Last modification：August 18, 2021