两数之和:
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
使用暴力法,执行两次遍历,当找出满足条件的数据时,提前结束循环。这种算法,最差条件下需要遍历n乘以n次数,时间复杂度也就是n平方。
为了优化暴力算法的最差情况,我们可以使用其他方式。因为要计算两个数据,所以是一一对应关系,我们可以很自然想到用c++中关联容器。
首先,题目中要求不能使用同一个数据。所以,我们初始化map时,如果是相同的元素,还需要判断元素所在数组序号。
然后再查找时,再判断对应元素的序号,去除找到同一个数据的情况。
最优解法:上述解法还是太常规思维了,我们可以只使用一次遍历,并结合关联容器就可以了。因为我们并不关心相同元素到底获取哪一个,所以,没必要保存相同元素所有的序号。