【算法题】找到数组中和为固定值的两个元素

在阅读的过程中有任何问题，欢迎一起交流

邮箱：1494713801@qq.com   

QQ：1494713801

题目：编写一个函数，输入为一个int型的数组numbers和一个int型变量target，找到这个数组中和为target的两个元素，输出其index。

假设每组输入有且仅有一组输出

Input: numbers={6, 2, 15, 7,11}, target=9

Output: index1=1, index2=2

解答：

两层遍历，最直观

时间复杂度：  O(N*N)

2.排序法

numbers按递增排序（快排），设置两个游标idx1和idx2

Idx1=0

Idx2=numbers.size

如果numbers[idx1]+numbers[idx2]==target，则要求的解为numbers[idx1]在原数列中的下标（现在的numbers是已经排序后的）和numbers[idx2]在原数列中的下标；

如果numbers[idx1]+numbers[idx2]>target，则idx2--；

如果numbers[idx1]+numbers[idx2]<target，则idx1++;

时间复杂度： O(N*logN)

3. 利用Map：

建立一个空Map，map中保存的是已经扫描过的number。

<K, V>为<numbers值，numbers下标>，

对于numbers[i]，如果map中存在K=target-numbers[i]，则要求的解为V（K=target-numbers对应的）和i；如果不存在，则向map中添加<numbers[i],i>

时间复杂度：O(N)

最后

以上就是高挑冬日最近收集整理的关于【算法题】找到数组中和为固定值的两个元素的全部内容，更多相关【算法题】找到数组中和为固定值内容请搜索靠谱客的其他文章。