一个小小的算法题：求两数之和

一个小小的算法题：求两数之和

具体需求：
给定一个整数数组，指定一个target值，通过整数数组里的两个值相加后结果等于target值。最后返回这两个值的索引值

举个例子：

number := []int{123,12,4,53, 66}
target := 16

number里的 12 + 4 = 16 
对应的下标是number[1] 和 number[2]

大概有两种写法：

第一种暴力算法，就是写两个for循环，通过对比两个数的方式来求出结果：

package main

import "fmt"

func main () {
  num := []int{12, 4, 6, 78, 9, 1, 66}
  target := 16

  for i := 0; i <= len(num) - 1; i++ {
    for j := 1; j <= len(num) - 1; j++ {
      if num[i] + num[j] == target {
        fmt.Println(i, j);
      }
    } 
  }
}

这样效率不是太高，如果需要处理的数很多，就会很耗时了

第二种写法：利用哈希查找法

package main

import "fmt"

func main() {
   num := []int{12, 3, 4, 63, 45, 6, 8, 7, 89, 9}
   target := 16

   //定义一个集合
   hasTable := map[int]int{}

   //循环处理
   for key, val := range num {
       //如果查找的值已经存在map里了，打印出结果值
       if index, ok := hasTable[target - val]; ok {
           fmt.Println(index, key);
           break;
       }

       //如果不存在，把值存进map里
       hasTable[val] = key
   }
}

这种写法省去了一层循环，代码看起来也相对更简洁了。查询效率相对第一种也提高了一些。

第二种的这种处理方式就是：[先把值存进哈希表里，然后通过相减的方式（target - n）求到结果]。第一次时，hasTable里一定是空的，接着会把值存进去，后面的第二次和N次循环时，如果target - n 后能求到结果，说明在此之前值已经存进去了。

简单的一道算法题，主要是为了练习一下算法！^_^

本作品采用《CC 协议》，转载必须注明作者和本文链接