2020-07-18:给定一个无序数组和一个目标值,找出数组中两个数之和等于目标值的所有组合,并指出其时间复杂度。

举报
福大大架构师每日一题 发表于 2020/08/19 11:05:49 2020/08/19
【摘要】 福哥答案2020-07-18:假设数组是[3,5,3,5],目标值是8。答案是否可重复,题里没说,所以分3种情况。如下:1.重复。答案是【0,1】【0,3】【1,2】【2,3】,序号组合,共4种组合。解法如下:1.1.嵌套遍历。时间复杂度:O(n^2)。1.2.哈希法。键存数组元素值,值存出现次数。时间复杂度:O(n)。1.3.排序+双指针夹逼。时间复杂度:O(nlogn)。2.半重复。答案...

福哥答案2020-07-18:

假设数组是[3,5,3,5],目标值是8。答案是否可重复,题里没说,所以分3种情况。如下:

1.重复。答案是【0,1】【0,3】【1,2】【2,3】,序号组合,共4种组合。
解法如下:
1.1.嵌套遍历。时间复杂度:O(n^2)。
1.2.哈希法。键存数组元素值,值存出现次数。时间复杂度:O(n)。
1.3.排序+双指针夹逼。时间复杂度:O(nlogn)。

2.半重复。答案是【0,1】【2,3】,也可能是【0,3】【1,2】,序号组合,共2种组合。
解法如下:
2.1.嵌套遍历。时间复杂度:O(n^2)。
2.2.哈希法。键存数组元素值,值存出现次数。时间复杂度:O(n)。
2.3.排序+双指针夹逼。时间复杂度:O(nlogn)。

3.不重复。答案是[3,5],值组合,共1种组合。
解法如下:
3.1.嵌套遍历。时间复杂度:O(n^2)。
3.2.哈希法。键存数组元素值,值不存。时间复杂度:O(n)。
3.3.排序+双指针夹逼。时间复杂度:O(nlogn)。
3.4.位图法。时间复杂度:O(目标值)。

代码采用3.2方式,用golang语言编写。代码如下:

package main
 
import "fmt"
 
func main() {
    nums := []int{3, 5, 3, 5, 4, 4}
    target := 8
    for k, _ := range twoSum(nums, target) {
        fmt.Println(k, "+", target-k, "=", target)
    }
}
 
func twoSum(nums []int, target int) map[int]struct{} {
    map0 := make(map[int]struct{}) //缓存,哈希保存
    ret := make(map[int]struct{})  //保存结果
 
    for i := 0; i < len(nums); i++ {
        complement := target - nums[i]     //差值 = 目标值-元素值
        if _, ok := map0[complement]; ok { //如果字典里有差值,说明已经找到了
            if complement < nums[i] {
                ret[complement] = struct{}{}
            } else {
                ret[nums[i]] = struct{}{}
            }
        }
        //如果字典里没有差值,缓存数组的当前值
        map0[nums[i]] = struct{}{}
    }
 
    return ret
}

执行结果如下:

image.png

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。