[LeetCode] 1.Two Sum 两数之和分析以及实现 (golang)
2024-08-30 05:07:40
题目描述：
/*
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
*/ 这道题给了我们一个数组，还有一个目标数target，让我们找到两个数字，使其和为target。首先想到的就是暴力搜索，遍历所有的组合项，获得结果，思路比较简单，代码如下：
func func1(s []int, tag int) []int {
for i := ; i < len(s)-; i++ {
for j := i + ; j < len(s); j++ {
if s[i]+s[j] == tag {
return []int{i, j}
}
}
}
return nil
}
这个算法的时间复杂度是O(n^2)。虽然节省了空间，但是时间复杂度高。尝试用空间换时间，使用一个HashMap，建立数字和其坐标位置之间的映射，在遍历数组的时候，用target减去遍历到的数字，就是另一个需要的数字了，直接在HashMap中查找其是否存在即可，那么代码就可这样写：
func func2(s []int, tag int) []int {
hash := make(map[int]int)
for i := ; i < len(s); i++ {
hash[s[i]] = i
}
for i := ; i < len(s); i++ {
temp := tag - s[i]
if _, ok := hash[temp]; ok {
if hash[temp] == i {
continue
}
return []int{i, hash[temp]}
}
}
return nil
}
这个算法的时间复杂度是O(n)。再想想，代码好像可以更加简洁一些，把两个for循环合并成一个：
func func3(s []int, tag int) []int {
hash := make(map[int]int, len(s))
for k, v := range s {
if j, ok := hash[tag-v]; ok {
return []int{j, k}
}
hash[v] = k
}
return nil
}
这样看起来就比较舒服ok了，完整的贴上来，运行一下试试吧。
package main import (
"fmt"
) func main() {
nums := []int{, , , }
target :=
s := func1(nums, target)
//s := func2(nums, target)
//s := func3(nums, target)
fmt.Printf("nums[%d]+nums[%d]=%d+%d=%d\n", s[], s[], nums[s[]], nums[s[]], target)
fmt.Printf("return [%d,%d]", s[], s[])
} //暴力破解 时间复杂度O（n^2）
func func1(s []int, tag int) []int {
for i := ; i < len(s)-; i++ {
for j := i + ; j < len(s); j++ {
if s[i]+s[j] == tag {
return []int{i, j}
}
}
}
return nil
} //用map辅助查找 时间复杂度O（n）
func func2(s []int, tag int) []int {
hash := make(map[int]int)
for i := ; i < len(s); i++ {
hash[s[i]] = i
} for i := ; i < len(s); i++ {
temp := tag - s[i]
if _, ok := hash[temp]; ok {
if hash[temp] == i {
continue
}
return []int{i, hash[temp]}
}
}
return nil
}
//优化一下，把两个for循环合并成一个
func func3(s []int, tag int) []int {
hash := make(map[int]int, len(s))
for k, v := range s {
if j, ok := hash[tag-v]; ok {
return []int{j, k}
}
hash[v] = k
}
return nil
}
最新文章
- 基于Quick-cocos2d-x的资源更新方案 二
- 15.6.2 Configuring the Merge Threshold for index pages[innodb]
- Java jstatd详解
- Oracle数据创建表空间
- 学习总结 html一般标签的使用
- XTUOJ 1252 Defense Tower 贪心
- 第四篇、CSS选择器
- 小公司生存，一般活过第一年，就能撑3年（读书笔记：成败关键，关键是你是否拥有现金流客户）good
- Hidden String（深搜）
- 行人检测(Pedestrian Detection)资源整合
- ios NSString拼接方法总结
- 快速开发 HTML5 交互式地铁线路图
- js 函数中的 return+匿名函数
- 常用的TCP选项
- git常用命令(转载自用)
- oracle-pl/sql之三
- php持续推送信息到客户端的方法
- Apache Commons Fileupload 反序列化漏洞分析
- Django之forms
- qemu模拟vexpress-a9及u-boot引导 linux