专栏首页祥子的故事两数之和(二)

两数之和(二)

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 大牛书单 | 人工智能方向好书推荐

    ? 导语:读书是一生的功课,技术人通过读书实现自我提升,学习优秀知识沉淀。TEG书知道本期特邀腾讯TEG AI Lab专家姚建华、腾讯TEG AI平台部工程平...

    腾讯技术工程官方号
  • 小甲鱼《零基础学习Python》课后笔记(十七):函数——Python的乐高积木

    1) 可以降低维护成本(函数只需修改def部分内容,而拷贝黏贴则需要每一处出现的地方都作修改)

    小火柴棒
  • Python使用Scrapy框架爬虫(一)

    1.首先我们需要安装scrapy模块,pip install scrapy ,不过这种方式经常会遇到许多未知的bug

    黄林晴
  • 小甲鱼《零基础学习Python》课后笔记(十三):元组——戴上了枷锁的列表

    7.上节课我们通过课后作业的形式学习到了“列表推导式”,那请问如果我把中括号改为小括号,会不会得到“元组推导式”呢?

    小火柴棒
  • 7个你现在应该学习python的理由

    Python 是一门更注重可读性和效率的语言,尤其是相较于 Java,PHP 以及 C++ 这样的语言,它的这两个优势让其在开发者中大受欢迎。

    用户4322765
  • 一日一技:在Python中,调用对象不存在的方法时自定义提示信息

    现在,我实例化这个类,并调用它的 play方法,由于这个方法不存在,所以现在必定导致报错,如下图所示。

    青南
  • AD16及AD18鼠标移动到网络后自动高亮设置

    小火柴棒
  • RGB_TTL、LVDS、MIPI接口液晶屏学习笔记

    液晶屏有RGB TTL、LVDS、MIPI DSI接口,这些接口区别于信号的类型(种类),也区别于信号内容。

    小火柴棒
  • 003-二维数组的查找

    在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个...

    单车变摩托
  • 小甲鱼《零基础学习Python》课后笔记(七、八):了不起的分支和循环1

    assert这个关键字我们称之为“断言”,当这个关键字后边的条件为假的时候,程序自动崩溃并抛出AssertionError的异常。

    小火柴棒

扫码关注云+社区

领取腾讯云代金券