Categories
力扣题解

力扣-两数之和

题目链接 https://leetcode-cn.com/problems/two-sum/ 解法一 两层循环,时间复杂度O(n^2),空间复杂度O(1)。 执行时间244ms,内存消耗9.3MB。 解法二 map记录数组元素与下标的映射关系,遍历一遍数组求解。时间复杂度O(n),空间复杂度O(n)。 执行时间20ms,内存消耗10.1MB。 解法三 用unordered_map构造映射,比map更快。因为map是用红黑树实现的,数据插入里面会排好序,搜索过程的时间复杂度为O(logn)。而unordered_map是用哈希表实现的,查找元素的时间复杂度为O(1)。 map适用于对内存大小敏感或数据要求有序性的情况;unordered_map适用于对查询效率要求较高的情况。 总得来说,这种解法的时间复杂度O(n),空间复杂度O(n)。耗时4ms,内存消耗10.3MB。