本文首发为CSDN博客，地址为：http://blog.csdn.net/xxzhangx/article/details/53428582
欢迎关注，谢谢！引用转载请注明作者和地址！
题目：给定一个整型的数组，找出其中的两个数使其和为某个指定的值，并返回这两个数的下标（数组下标是从0开始）。假设数组元素的值各不相同，则要求时间复杂度为O(n)，n为数组的长度。
伪代码：
int [] twoSum(int [] A,int target){
int[] res = {-1,-1};
if (A =null || A.length< 2) return res;
HashMap < Integer,Integer> hm = new HashMap <Integer,Integer>();
for(int i =0;i<A.length;i++){
//扫描一遍，存储值与下标
hm.put(A[i],i);
}
for (int i =0;i<A.length;i++){
if(hm.containsKey(target-A[i]) && target != 2*A[i]){
//获取结果的两个下标
res[0] = i;
res[1] == hm.get(target - A[i]);
break;
}
}
return res;
}
伪代码中使用了hash方法，由于不熟悉，故采用类似的方法来做。时间复杂度上可能不符合题意。
R语言：
> res <- list()
> index <- list()
> k =0
> i = 1
> two_sum_2<-function(a,target)
{
if (is.null(a) || length(a) < 2)
{
return("zeros or length is too small")
}
if((length(unique(a))) < length(a))
{
return("some value repteaed")
}
else
{
for (i in 1:length(a))
{
if(is.element(target-a[i],a))
{
k = k + 1
res[[k]] = c(a[i],target - a[i])
j = which(a==(target - a[i]))
index[[k]] = append(res[[k]],c(i,j))
i = i +1
}
}
}
return (index)
}
> a= c(1:10,20:30)
> two_sum_2(a,30)
[[1]]
[1] 1 29 1 20
[[2]]
[1] 2 28 2 19
[[3]]
[1] 3 27 3 18
[[4]]
[1] 4 26 4 17
[[5]]
[1] 5 25 5 16
[[6]]
[1] 6 24 6 15
[[7]]
[1] 7 23 7 14
[[8]]
[1] 8 22 8 13
[[9]]
[1] 9 21 9 12
[[10]]
[1] 10 20 10 11
[[11]]
[1] 20 10 11 10
[[12]]
[1] 21 9 12 9
[[13]]
[1] 22 8 13 8
[[14]]
[1] 23 7 14 7
[[15]]
[1] 24 6 15 6
[[16]]
[1] 25 5 16 5
[[17]]
[1] 26 4 17 4
[[18]]
[1] 27 3 18 3
[[19]]
[1] 28 2 19 2
[[20]]
[1] 29 1 20 1
> a=c(1:10,2:10,3:11)
> two_sum_2(a,30)
[1] "some value repteaed"
不足的是有重复计数。
python:
res = []
def two_sum_2(a,target):
if ((a == None) or (len(a) < 2)):
return ("zeros or length is too small")
elif (len(a) > len(set(a))):
return ("some value repteaed")
else:
for i in range(len(a)):
if (target - a[i]) in a :
j = a.index(target - a[i])
res.append([a[i],target-a[i],[i,j]])
return (res)
b = [1]
print (two_sum_2(b,target=2))
zeros or length is too small
b = [1,2,4,5,1,3,2,1]
print (two_sum_2(b,target=2))
some value repteaed
b = [1,2,3,4,5]
print (two_sum_2(b,target=6))
[[1, 5, [0, 4]], [2, 4, [1, 3]], [3, 3, [2, 2]], [4, 2, [3, 1]], [5, 1, [4, 0]]]
拓展
如果数组可能出现相同值的元素，那么上述算法还能正确解决吗？
答案是：可以的
R语言：
res <- list()
index <- list()
k =0
i = 1
two_sum_2<-function(a,target)
{
if (is.null(a) || length(a) < 2)
{
return("zeros or length is too small")
}
else
{
for (i in 1:length(a))
{
if(is.element(target-a[i],a))
{
k = k + 1
res[[k]] = c(a[i],target - a[i])
j = which(a==(target - a[i]))
index[[k]] = append(res[[k]],c(i,j))
i = i +1
}
}
}
return (index)
}
> a=c(1:10,2:10,3:11)
> two_sum_2(a,6)
[[1]]
[1] 1 5 1 5 14 22
[[2]]
[1] 2 4 2 4 13 21
[[3]]
[1] 3 3 3 3 12 20
[[4]]
[1] 4 2 4 2 11
[[5]]
[1] 5 1 5 1
[[6]]
[1] 2 4 11 4 13 21
[[7]]
[1] 3 3 12 3 12 20
[[8]]
[1] 4 2 13 2 11
[[9]]
[1] 5 1 14 1
[[10]]
[1] 3 3 20 3 12 20
[[11]]
[1] 4 2 21 2 11
[[12]]
[1] 5 1 22 1
python:
res = []
def two_sum_2(a,target):
if ((a == None) or (len(a) < 2)):
return ("zeros or length is too small")
else:
for i in range(len(a)):
if (target - a[i]) in a :
j = a.index(target - a[i])
res.append([a[i],target-a[i],[i,j]])
return (res)
b = [1,2,4,5,1,3,2,1]
print (two_sum_2(b,target=2))
[[1, 1, [0, 0]], [1, 1, [4, 0]], [1, 1, [7, 0]]]
