题目描述:
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]。
题目的话,没有什么好分析的,相信大家都能够看得懂,关键是使用什么样的方法去完成。通常来说越是简单的题目,越会有一些简单的方法。
通常来说,我们做算法题目的时候,一开始可能想不到最佳的方法,这时候我们可以使用最粗暴的方法-暴力破解法。然后在此基础上实现优化,找到更佳的方法。
暴力破解法
使用暴力破解法,其时间复杂度为O(n^2)。其中仔细分析里面的for循环实现的就是查找一个数能够和数组中的元素相加等于目标值。这个要查找的数可以表示为target - nums[i]。这个问题可以简化为在数组中查找一个数是否存在,而且这个数是唯一的。这里我们就可以想到对象的一个特点:对象的属性是唯一的。也就是如果我们把这个数作为对象的属性,通过对象的属性的唯一性来判断其是否存在。