• 129136

    文章

  • 809

    评论

  • 12

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

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

服了这份高薪指南,涨多少你说了算>>

福哥答案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
}

执行结果如下:


评论


695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

0条评论

Loading...


发表评论

电子邮件地址不会被公开。 必填项已用*标注

自定义皮肤 主体内容背景
打开支付宝扫码付款购买视频教程
遇到问题联系客服QQ:419400980
注册梁钟霖个人博客