本文首发为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中能否改为字典呢？