给定一个target，问：数组是否有两个元素的和为target；

清疚 2022-05-21 04:06 278阅读 0赞

转载：https://blog.csdn.net/u010515761/article/details/43451035

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

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

示例 ：

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

Output: index1=1, index2=2

Center

解答：

  1. 查找法

两层遍历，最直观

时间复杂度： 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)

  1. 利用Map：

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

为，

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

时间复杂度：O(N)

Center 1

发表评论

表情：
评论列表 （有 0 条评论，278人围观）

还没有评论，来说两句吧...

相关阅读