本文首發(fā)為CSDN博客辞嗡，地址為：http://blog.csdn.net/xxzhangx/article/details/53428582
歡迎關(guān)注稼稿，謝謝硫嘶！引用轉(zhuǎn)載請(qǐng)注明作者和地址淘太！
題目：給定一個(gè)整型的數(shù)組啊终，找出其中的兩個(gè)數(shù)使其和為某個(gè)指定的值疑苔，并返回這兩個(gè)數(shù)的下標(biāo)（數(shù)組下標(biāo)是從0開始）甫匹。假設(shè)數(shù)組元素的值各不相同，則要求時(shí)間復(fù)雜度為O(n)惦费，n為數(shù)組的長(zhǎng)度兵迅。
偽代碼：
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++){
//掃描一遍，存儲(chǔ)值與下標(biāo)
hm.put(A[i],i);
}
for (int i =0;i<A.length;i++){
if(hm.containsKey(target-A[i]) && target != 2*A[i]){
//獲取結(jié)果的兩個(gè)下標(biāo)
res[0] = i;
res[1] == hm.get(target - A[i]);
break;
}
}
return res;
}
偽代碼中使用了hash方法薪贫，由于不熟悉恍箭，故采用類似的方法來做。時(shí)間復(fù)雜度上可能不符合題意瞧省。
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"
不足的是有重復(fù)計(jì)數(shù)扯夭。
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]]]
拓展
如果數(shù)組可能出現(xiàn)相同值的元素，那么上述算法還能正確解決嗎鞍匾？
答案是：可以的
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]]]
