本文首发为CSDN博客，地址为：http://blog.csdn.net/xxzhangx/article/details/53420042
欢迎关注，谢谢！引用转载请注明地址和作者！
题目：给定一个整型数组，是否能找出其中的两个数使其和为某个指定的值？
注意：这里对数据没有限制，表明数据中允许存在重复值
伪代码：
boolean hasSum(int[] A, int target){
boolean res = false;
if(A ==null || A.length<2) return res;
Arrays.sort(A);
int i =0,j=A.length-1;
while (i <j){
if(A[i]+A[j] == target){
res = true;
break;
}else if (A[i]+A[j] > target){
//目标值过小，则向前移动尾部指针，减小两数之和；
j--;
}else{
//目标值过大，则向后移动首部指针，增加两数和；
i++;
}
}
return res;
}
有了这个伪代码，代码就好写。下面用R语言和python写：
R语言
> a= c(1:10,2:11,1:3,2:8,2:9)
> res = list()
> index = list()
> aa = function(a,target=NULL)
{
if (length(a) < 2)
{
return (res)
}
a1 = sort(a);
i = 1;j=length(a);k=0;
while(i < j)
{
if (a1[i]+a1[j] == target)
{
k=k+1;
res[[k]] = c(a1[i],a1[j]);
index[[k]] = append(res[[k]],c(i,j));
i = i +1;
j = j -1;
}
else if (a1[i]+a1[j]>target)
{
j = j -1;
}
else
{
i = i +1;
}
}
return (index)
}
> aa(a,6)
[[1]]
[1] 1 5 1 20
[[2]]
[1] 1 5 2 19
[[3]]
[1] 2 4 3 16
[[4]]
[1] 2 4 4 15
[[5]]
[1] 2 4 5 14
[[6]]
[1] 2 4 6 13
[[7]]
[1] 3 3 8 12
[[8]]
[1] 3 3 9 11
得到了等于6的两个数，还得到了在排序后它们的位置。
python
1、暴力法
# -*- coding: utf-8 -*-
a = [1,2,3,4,2,1,2,3,4,5,6,4,5,6,4,3,2,2,1,3,4,5,6,7,8,5,4,3,2,1]
len1 = len(a)
target = 6
#number = map(int,a)
for i in range(len1):
for j in range(i+1,len1):
if a[i] + a[j] == target:
print "the two number are %d and %d ,the index are %d and %d " % (a[i],a[j],i+1,j+1)
the two number are 1 and 5 ,the index are 1 and 10
the two number are 1 and 5 ,the index are 1 and 13
the two number are 1 and 5 ,the index are 1 and 22
the two number are 1 and 5 ,the index are 1 and 26
the two number are 2 and 4 ,the index are 2 and 4
the two number are 2 and 4 ,the index are 2 and 9
the two number are 2 and 4 ,the index are 2 and 12
the two number are 2 and 4 ,the index are 2 and 15
the two number are 2 and 4 ,the index are 2 and 21
the two number are 2 and 4 ,the index are 2 and 27
the two number are 3 and 3 ,the index are 3 and 8
the two number are 3 and 3 ,the index are 3 and 16
the two number are 3 and 3 ,the index are 3 and 20
the two number are 3 and 3 ,the index are 3 and 28
the two number are 4 and 2 ,the index are 4 and 5
the two number are 4 and 2 ,the index are 4 and 7
the two number are 4 and 2 ,the index are 4 and 17
the two number are 4 and 2 ,the index are 4 and 18
the two number are 4 and 2 ,the index are 4 and 29
the two number are 2 and 4 ,the index are 5 and 9
the two number are 2 and 4 ,the index are 5 and 12
the two number are 2 and 4 ,the index are 5 and 15
the two number are 2 and 4 ,the index are 5 and 21
the two number are 2 and 4 ,the index are 5 and 27
the two number are 1 and 5 ,the index are 6 and 10
the two number are 1 and 5 ,the index are 6 and 13
the two number are 1 and 5 ,the index are 6 and 22
the two number are 1 and 5 ,the index are 6 and 26
the two number are 2 and 4 ,the index are 7 and 9
the two number are 2 and 4 ,the index are 7 and 12
the two number are 2 and 4 ,the index are 7 and 15
the two number are 2 and 4 ,the index are 7 and 21
the two number are 2 and 4 ,the index are 7 and 27
the two number are 3 and 3 ,the index are 8 and 16
the two number are 3 and 3 ,the index are 8 and 20
the two number are 3 and 3 ,the index are 8 and 28
the two number are 4 and 2 ,the index are 9 and 17
the two number are 4 and 2 ,the index are 9 and 18
the two number are 4 and 2 ,the index are 9 and 29
the two number are 5 and 1 ,the index are 10 and 19
the two number are 5 and 1 ,the index are 10 and 30
the two number are 4 and 2 ,the index are 12 and 17
the two number are 4 and 2 ,the index are 12 and 18
the two number are 4 and 2 ,the index are 12 and 29
the two number are 5 and 1 ,the index are 13 and 19
the two number are 5 and 1 ,the index are 13 and 30
the two number are 4 and 2 ,the index are 15 and 17
the two number are 4 and 2 ,the index are 15 and 18
the two number are 4 and 2 ,the index are 15 and 29
the two number are 3 and 3 ,the index are 16 and 20
the two number are 3 and 3 ,the index are 16 and 28
the two number are 2 and 4 ,the index are 17 and 21
the two number are 2 and 4 ,the index are 17 and 27
the two number are 2 and 4 ,the index are 18 and 21
the two number are 2 and 4 ,the index are 18 and 27
the two number are 1 and 5 ,the index are 19 and 22
the two number are 1 and 5 ,the index are 19 and 26
the two number are 3 and 3 ,the index are 20 and 28
the two number are 4 and 2 ,the index are 21 and 29
the two number are 5 and 1 ,the index are 22 and 30
the two number are 5 and 1 ,the index are 26 and 30
the two number are 4 and 2 ,the index are 27 and 29
暴力法复杂度较高，下面做下修改：
# -*- coding: utf-8 -*-
res = []
def sum_two_1(a,target):
if (len(a) < 2):
return (0)
a1 =sorted(a)
i=0;j=len(a1)-1;k=0;
while(i<j):
if (a1[i]+a1[j] == target):
k=k+1
res.append([a1[i],a1[j],[i,j]])
i = i + 1
j = j -1
elif(a1[i]+a1[j] > target):
j = j -1
else:
i = i +1
return(res)
if __name__ == "__main__":
a = [1,2,3,4,2,1,2,3,4,5,6,4,5,6,4,3,2,2,1,3,4,5,6,7,8,5,4,3,2,1]
print(sum_two_1(a,int(4)))
[[1, 3, [0, 14]], [1, 3, [1, 13]], [1, 3, [2, 12]], [1, 3, [3, 11]], [2, 2, [4, 9]], [2, 2, [5, 8]], [2, 2, [6, 7]]]
在python中能否改为字典呢？
