哈希查询 两数之和

如同for循环增量在不同的位置影响循环体边控,哈希读写亦如是

题面

给出一个整数数组,请在数组中找出两个加起来等于目标值的数,
你给出的函数twoSum 需要返回这两个数字的下标(index1,index2),需要满足 index1 小于index2.。

注意:下标是从1开始的 假设给出的数组中只存在唯一解
例如:
给出的数组为 {20, 70, 110, 150},目标值为90
输出 index1=1, index2=2

分析

  • 暴力破解双层循环
  • 确保使用的哈希,在查询之后收录当前索引位

哈希实现

一次循环解决哈希读写,递增索引查询

func twoSum( numbers []int ,  target int ) []int {
    m := make(map[int]int,0)
    for i,v := range numbers {
        if idx, ok := m[target-v];ok{
            return []int{idx,i+1}
        }
        m[v]=i+1
    }
    return nil
}

暴力破解

func twoSum( numbers []int ,  target int ) []int {
    for i:=0;i<len(numbers);i++ {
        for j:=i+1;j<len(numbers);j++{
            if numbers[i] + numbers[j] == target {
                return []int{i+1,j+1}
            }
        }
    }
    return nil
}

数对和

找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对

输入: nums = [5,6,5], target = 11
输出: [[5,6]]

哈希查询成功,当前循环变量数不入哈希,对应哈希计数减记

func pairSums(nums []int, target int) [][]int {
    rs := [][]int{}
    m := make(map[int]int, 0)
    for _,v := range nums{
        if cnt,ok := m[target-v];ok && cnt > 0{
            rs = append(rs, []int{target-v, v})
            m[target-v]--
        }else{
            m[v]++
        }
    }
    return rs
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
115
粉丝
13
喜欢
87
收藏
43
排名:101
访问:4.6 万
私信
所有博文