问答

当前位置
  • 首页
  • 问答
  • 610.Two Sum (difference == target)和608.Two Sum II (sum == target)相向vs同向双指针解法

610.Two Sum (difference == target)和608.Two Sum II (sum == target)相向vs同向双指针解法

  • Ta: 徐子懋

对比这两道题,他们的各种解法是否相通?以下分析的时间复杂度又是否正确呢?

  1. Two Sum - Difference equals to target 解法:

1.(标解)同向双指针从左往右遍历(两数之差小于target往右移动右指针,大于target往右移动左指针):O(n),每个元素最多被访问了两遍

2.同向双指针从右往左遍历(两数之差小于target往左移动左指针,大于target往左移动右指针):O(n),每个元素最多被访问了两遍

3.相向双指针以右指针为外循环左为内循环(两数之差大于target往右移动左指针,小于target把左指针停在上一个元素,再往左移动右指针;如果左右指针相遇,重置左指针指向第一个元素,再往左移动右指针):有O(n)的时候,也有最坏O(n^2)的时候;比如:
[1,3,4,10,11,15]
target=6, so output is indices for [4,10]: O(n)
target=2, so output is indices for [1,3]: O(n^2)

4.相向双指针以左指针为外循环右为内循环(两数之差大于target往左移动右指针,小于target把右指针停在上一个元素,再往右移动左指针;如果左右指针相遇,重置右指针指向最后元素,再往右移动左指针):有O(n)的时候,也有最坏O(n^2)的时候,例子如上。

所以O(n)的情况是属于平均复杂度吗?面试的时候是否两个时间复杂度都要提及?

-------

  1. Two Sum II - Input array is sorted (sum equals to target) 解法:
    1.同向双指针从左往右遍历(两数之和小于target往右移动右指针,大于target把右指针停在上一个元素,再往右移动左指针;如果右指针到尾了,往右移动左指针,再重置右指针指向左指针之后一个元素):有O(n)的时候,也有最坏O(n^2)的时候;比如:
    [1,3,4,6,11,15]
    target=10, so output is indices for [4,6]: O(n)
    target=19, so output is indices for [4,15]: O(n^2)

2.同向双指针从右往左遍历(两数之和大于target往左移动左指针,小于target把左指针停在上一个元素,再往左移动右指针;如果左指针到头了,往左移动右指针,再重置左指针指向右指针左边一个元素):有O(n)的时候,也有最坏O(n^2)的时候;比如:
[1,4,6,10,11,12]
target=10, so output is indices for [4,6]: O(n^2)
target=14, so output is indices for [4,10]: O(n)

3.(标解)相向双指针以右指针为外循环左为内循环(两数之和小于target往右移动左指针,大于target往左移动右指针):O(n),每个元素最多被访问了两遍

4.相向双指针以左指针为外循环右为内循环(两数之和大于target往左移动右指针,小于target往右移动左指针):O(n),每个元素最多被访问了两遍

--------

问题1.其实这两道题的上述O(n^2)的解法(即两数之差的双向指针解法,和两数之和的单向指针解法,不同于暴力枚举)是不是所有情况下都能解呢?

问题2.所以是不是对于指针题,任何能用同向双指针从左往右遍历的解法,都能从相反方向遍历来解?任何能用相向双指针以右指针为外循环左为内循环的,也都能调换内外循环指针来解?

0 个回复

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1