专栏首页优雅R「LeetCode」0001-两数之和

「LeetCode」0001-两数之和

难度:简单。

参考:

  • https://leetcode-cn.com/problems/two-sum[1]
  • https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0001.Two-Sum/[2]

代码仓库:https://github.com/ShixiangWang/LeetCode[3]

问题

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

示例:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

题解

顺序扫描数组,对每一个元素,在 map 中找能组合给定值的另一半数字,如果找到了,直接返回 2 个数字的下标即可。如果找不到,就把这个数字存入 map 中,等待扫到“另一半”数字的时候,再取出来返回结果。

这种解法将数据扫描一遍必然得到结果,所以时间复杂度是 O(n)。

Go

package main

import "fmt"

func twoSum(nums []int, target int) []int {
  m := make(map[int]int)
  for i := 0; i < len(nums); i++ {
    another := target - nums[i]
    if _, ok := m[another]; ok {
      return []int{m[another], i}
    }
    m[nums[i]] = i
  }
  return nil
}

func main() {
  fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
  fmt.Println(twoSum([]int{3, 2, 4}, 6))
}

运行结果:

[Running] go run "/Users/wsx/Documents/GitHub/LeetCode/LeetCode/leetcode/0001-two-sum/main.go"
[0 1]
[1 2]

R

依据题解和Go的实现思路,不难写出R的对应程序。不过考虑到语言之间的差异,值得注意的有几点:

  1. R本身不自带纯粹的字典实现。我们使用c()构造命名向量,但需要注意该向量是支持整数索引的,所以当我们使用输入序列作为键时,都必须使用相应的字符串形式。
  2. R是以1作为索引起始,为了保持结果一致,最后返回值统一减去1。
twoSum <- function(nums, target) {
  # stopifnot(length(target) == 1, is.numeric(nums), is.numeric(target))
  m <- c()
  for (i in seq_along(nums)) {
    another <- target - nums[i]
    if (length(m) > 0 && !is.na(m[as.character(another)])) {
      return(c(as.integer(m[as.character(another)]), i) - 1L) # R 是1开始索引的编程语言,这里做一个-1处理
    }
    m[as.character(nums[i])] = i
  }
  return(NULL)
}

cat(twoSum(c(2, 7, 11, 15), 9))
cat("\n")
cat(twoSum(c(3, 2, 4), 6))

运行结果:

[Running] Rscript "/Users/wsx/Documents/GitHub/LeetCode/LeetCode/leetcode/0001-two-sum/main.R"
Using library: /Users/wsx/Library/R
0 1
1 2

参考资料

[1]

https://leetcode-cn.com/problems/two-sum: https://leetcode-cn.com/problems/two-sum

[2]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0001.Two-Sum/: https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0001.Two-Sum/

[3]

https://github.com/ShixiangWang/LeetCode: https://github.com/ShixiangWang/LeetCode

本文分享自微信公众号 - 优雅R(elegant-r),作者:王诗翔

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-06-30

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 上榜了......

    不少录友应该在我的Github上看算法文章,项目地址:https://github.com/youngyangyang04/leetcode-master

    代码随想录
  • LeetCode之两数之和

    大话swift
  • 【LeetCode】两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

    弗兰克的猫
  • LeetCode - 两数之和

    开启新的一个篇章,LeetCode题解,个人的一些解题思路分享(可能有的题目就是这么菜,之后慢慢更,可以先把自己做完的100多题每天1题的方式先发出来,一遍更一...

    晓痴
  • LeetCode | 两数之和

    努力在北京混出人样
  • leetcode - 两数之和

    给定一个整数数组nums和一个整数目标值target,请你在该数组中找出 和为目标值 的那两个 整数,并返回它们的数组下标。

    璀错
  • Leetcode:两数之和

    今年准备刷一下leetcode,提升一下算法相关的能力。从最简单的开始刷起,各位大佬不要嘲笑我。不知道能坚持多久。

    Liusy
  • Leetcode 两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    Meng小羽
  • LeetCode | 两数之和

    努力在北京混出人样
  • LeetCode---两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    TrueDei
  • [不定时一题]Leetcode两数之和

    今天又是神奇的一天,今天是小编默默的打开了Leetcode题库的第一天,初生牛犊不怕虎,开足马力就是干。

    小丑同学
  • 【LeetCode】两数之和

    Jacob丶
  • LeetCode - 两数之和②

    原题地址:https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

    晓痴
  • LeetCode:两数之和

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

    微客鸟窝
  • LeetCode 两数之和 Python

  • 【LeetCode】1.两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    Delevin
  • leetcode:1 两数之和

    贵哥的编程之路
  • 【LeetCode】两数之和day09

    居士
  • LeetCode | 1.两数之和

    上面的题就是 两数之和 题目的截图,同时 LeetCode 会根据选择的语言给出了一个类的定义或者函数的定义,然后在其中实现 两数之和 的解题过...

    码农UP2U

扫码关注云+社区

领取腾讯云代金券