Lintcode56 Two Sum solution 题解

【题目描述】

Given an array of integers, 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.

Notice:You may assume that each input would have exactly one solution

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 1 到 n，不是以 0 开头。

注意:你可以假设只有一组答案。

【题目链接】

www.lintcode.com/en/problem/two-sum/

【题目解析】

三种解法。

解法一， hash

从左往右扫描一遍，然后将数及坐标，存到map中。然后再扫描一遍即可。时间复杂度O(n)

解法二，双指针扫描

将数组排序，然后双指针从前后往中间扫描。时间复杂度O(n*lgn)。因为是要求返回原数组的下标，所以在排序的时候还得有额外的数组来存储下标信息， 也挺麻烦。

解法三，暴力搜索

这个倒是最省事的。时间复杂度O(n*n)

【参考答案】

www.jiuzhang.com/solutions/two-sum/