两数之和（二）

努力在北京混出人样

发布于 2019-02-18 15:39:06

3730

发布于 2019-02-18 15:39:06

题目：给定一个整型的数组，找出其中的两个数使其和为某个指定的值，并返回这两个数的下标（数组下标是从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]]]

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016年12月02日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法