未分类
Python算法
两数之和（two-sum） 这是LeetCode上一道十分经典的题目，存在多种解法，难度是简单，但后面难度更高的三数之和、四数之和，其实也是由这道题演变而来的。 题目 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum 解题 方法一： 暴力法 暴力法很逻辑很简单，采用两轮错位嵌循环，计算两个位置的数字之和是否等于目标值，因为题目中说明了只有两个整数的和是等于target，所以一旦找到直接 return 就行，十分简单粗暴。
|
1 2 3 4 5 6 |
class Solution(object): def twoSum(self, nums, target): for i in range(len(nums) - 1): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return i, j |
这种写法很好理解，得益于Python语言的简洁，上面核心部分的代码甚至可以简化为一行：
|
1 |
chain.from_iterable([[i, j] for i in range(len(nums) - 1) for j in range(i + 1, len(nums)) if nums[i] + nums[j] == target]) |
因为是嵌套循环，所以时间复杂度是O(N^2N2)，空间复杂度是O(1)，提交了也没毛病，在所有 python 提交中击败了31.08%的用户，这种方法在运行效率上不是很高。面试时如果没有太好的思路，可以尝试用暴力法来解决。如果能在短时间内写出上面的代码，至少说明你对语言本身还是很熟练的，代码的功底也还可以。 方法二：哈希大法 正确的思路是采取空间换时间的办法，使用一个哈希表缓存。思路如下： 题目要求我们找出两个和为target的数，也就是 nums[i] Read more…