LintCode两数之和，三数之和，四数之和
原文作者：eudiwffe
原文链接：http://www.cnblogs.com/eudiwffe/p/6282635.html
LintCode有大部分题目来自LeetCode，但LeetCode比较卡，下面以LintCode为平台，简单介绍我AC的几个题目，并由此引出一些算法基础。
1）两数之和（two-sum）
题目编号：56，链接：http://www.lintcode.com/zh-cn/problem/two-sum/
题目描述：
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。
你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 1 到 n，不是以 0 开头。
注意：你可以假设只有一组解。
样例：给出 numbers = [2, 7, 11, 15], target = 9, 返回 [1, 2]，即数字2,7
代码接口：
| 1 2 3 4 5 6 7 8 9 10 11 |
class Solution
{
public:
/*
*
@param numbers : An array of Integer
*
@param target : target = numbers[index1] + numbers[index2]
*
@return : [index1+1, index2+1] (index1 < index2)
*/
vector<int>
twoSum(vector<int>
&nums, int target)
{
//
write your code here
}
};
|
常见的思路是：两层for循环，任意两个数组合求其和，判断是否等于给定的target。但这样太慢，需要O(n^2)的时间，O(1)的额外空间。可以反过来思考，假如当前选择了一个数字a，那么为了满足条件，另一个数字b必须满足：b=targe-a，即在数组中寻找是否存在b。
如何快速寻找数组中是否存在一个数字b？假如数组是有序的，可以使用二分查找方法，其查找时间复杂度是O(logn)。然而题目并没给定这个条件。如果对数组排序，首先就要O(nlogn)的时间进行排序，并且排序后，数字的原始下标也要保存，显然需要O(nlogn)的时间以及O(n)的空间，并不是最好的方法。
如何对一个数组进行快速查找一个元素？算法中提供了一种方法——哈希（Hash），即对数组中的每个元素按照某种方法（hash function）计算其“唯一”值id（称为哈希值），存储在新的数组A中（一般称为哈希数组），并且其下标就是这个“唯一”值。那么如果访问A[id]存在，则这个元素存在，否则，原始数组中不存在该元素。由于数组是顺序存储的支持随机访问，所以查找一个元素是否在数组中，只需要O(1)的时间，但是在初始化哈希数组时，需要O(n)的时间和O(n)的空间。对于某些特定应用中，需要快速的时间，而对空间要求不苛刻时，哈希数组是一个非常好的方法。为了能够满足各种应用场景，又衍生出容量大小可以动态增长的哈希集合(hash set)、哈希映射(hash map)，STL提供了关于哈希的两个类：unordered_set和unordered_map，前者只存储元素，后者可以再增加额外的标志信息。详细的内容，请自行补充。
由于构造的哈希数组，其元素的下标已经改变了，所以需要额外存储元素原始的下标，因此此题使用unordered_map<int,int>，其存储的内容为<元素值，元素原始下标>，详细代码：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution
{
public:
/*
*
@param numbers : An array of Integer
*
@param target : target = numbers[index1] + numbers[index2]
*
@return : [index1+1, index2+1] (index1 < index2)
*/
/*
Tips: find any pair is ok not all pairs.
*
using hash map to store the num value and index
*
notice: if the target is 4 and the answer expection num 2 + 2,
*
only the one num 2 is stored in hash map, but also work ok!
*
because must have the other num 2 is not in hash map!
*
*/
vector<int>
twoSum(vector<int>
&nums, int target)
{
//
write your code here
vector<int>
v(2,0);
unordered_map<int,int>
hash;//
val+id
//
we can search num and insert it to hash map at same time
//
and current num must be not in hash map
for(int i=nums.size();
i--; hash[nums[i]]=i){
if (hash.find(target-nums[i])
== hash.end()) continue;
|
