[LeetCode]167. Two Sum II – Input array is sorted 两个数的和第二季 – 输入的数组被排序好

题目地址:(?)

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

题目描述:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目大意:

提供一个整形数组,并且该数组已经以从小到大排序完毕,寻找两个加起来为一个特殊目标数字的数字。

这个函数 twoSum 应该返回两个数字下标并且将这两个坐标对应数字加起来为目标数字。那个 index1 一定要小于 index2。请记录你返回的答案(index1 和 index2)并不是从 0 开始。

你可能假设每一个输入都有确定的一个解答。

输入:numbers={2, 7, 11, 15}, target=9

输出:index1=1, index2=2

 


现在我觉得我的思路很狭窄。看了答案之后的我感觉很羞耻。

以下是我的超时的代码。

这个代码虽然它只有一个 for ,但是其中 i 不动,j 动的情况有非常多。其实等同于两层 for 循环。超时的样例输出告诉我它输入了一个非常多 0 和非常多 9 ,只在 0 与 9 之间写了2 和 3 ,目标数字是 5 。那这真的没有办法肯定是超时的了。因为不可能遍历两次这么多的数字。

然后我竟然去用哈希容器 unordered_map 和 set想把相同的数字抹去,因为 set 有去重复的特性。可是这两个容器的指针是直接指向它的地址,额我的意思是,在我的猜测中,就是说他有加 & 符号,在实现的时候就是加这个。所以遍历是无法重复遍历的。就是说你走过去了,就不给你回头路了。

然后没做出来,没做出来就查答案。

答案地址:http://www.cnblogs.com/ganganloveu/p/4198968.html

“(引用)

典型的双指针问题。

初始化左指针left指向数组起始,初始化右指针right指向数组结尾。

根据已排序这个特性,

(1)如果numbers[left]与numbers[right]的和tmp小于target,说明应该增加tmp,因此left右移指向一个较大的值。

(2)如果tmp大于target,说明应该减小tmp,因此right左移指向一个较小的值。

(3)tmp等于target,则找到,返回left+1和right+1。(注意以1为起始下标)

时间复杂度O(n): 扫一遍

空间复杂度O(1)

ps: 严格来说,两个int的加和可能溢出int,因此将tmp和target提升为long long int再进行比较更鲁棒。

可以看到,它只遍历了一遍,确是运用从小到大排序的特性,根据这个临时结果与目标的大小关系,对左右指针进行操作。其实我看到这个答案的时候第一反应是前几天做到的那题 Product of Array Except Self 。那道题先左了左右两边数组的赋值,然后在左边加右边。这题其实,我有想到左右两边一起走,奈何冒泡排序的思维定势还有“如果 numbers[i] 比目标大的话,这个 for 循环其实就可以停止了”,这种愚蠢的想法,所以我就一直跳进这个很糟糕的圈子里出不来。

在网上闲逛了一下,大家的做法都类似于上面这位前辈,都是左右指针互相比较。我看到那个题目里的 Tags 写了一个 Two pointers ,其实我只想到了两个下标操作。

其实这种算法思路我也渐渐理解了。很多时候一个问题可以被拆成两个部分去做。

最后上一下我的 Accept 代码:

167. Two Sum II – Input array is sorted