Java教程

算法入门: 两数之和

本文主要是介绍算法入门: 两数之和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:

	给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那两个整数,
	并返回它们的数组下标。

题目分析:

	数组中找到两个数相加的值为指定的某个值。这两个数一定为一对。

解题:
解法1:

使用暴力的方法,target减去数组中的整数,然后与其他整数去判断。这样就是一个双层循环。第一层循环target-
nums[i]得到值X,然后第二层去循环数组寻找等于X的下表。第一层时间复杂度N,第二层时间复杂度N,两者具
有关联最终时间复杂度:N^2。空间复杂度O(1)

解法2:

	对于暴力循环的方法,我们第一层target - nums[i]得到值X,依旧保留,但是第二层时,如果我们把数组放入
	hash中,那么X只需判断一次O(1)。相对于每个X都要和数组其他数进行判断时间复杂度降低很多O(N)。这样就
	有一个问题,何时将数组元素写入hash呢?这时借助题目分析中两个数一定是一对,我们可以在判断X等于数组
	值时,如果不相等就写入hash,相等就是我们要的结果。
func twoSum(nums []int, target int) []int {
   hashtable := make(map[int]int,len(nums))
   for i,j := range nums{
       if v,ok := hashtable[target - j] ;ok{
           return []int{i,v}
       }
       hashtable[j] = i
   }
   return nil
}

题目链接:https://leetcode-cn.com/problems/two-sum

这篇关于算法入门: 两数之和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!