![](/images/13-1.png)
暴力
暴力查找,两层 for 循环搞定。唯一要注意的点就是题干要求数组中同一个元素不能使用两遍,所以内层循环要取外层循环之后的元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return null; }
|
两层循环,时间复杂度为 O(n ^ 2);没有用到额外空间,空间复杂度为 O(1)。
时间复杂度推导:
- 最好时间复杂度为 O(1),比如 {2, 7, 11, 15}, target 为 9
- 最坏时间复杂度为 (n - 1) + (n - 2) + (n - 3) + … + 1 = (n - 1) * (n / 2),省略低阶和常量,结果为 O(n ^ 2)
两遍哈希表
之前在归并排序的文章中说过,如果数据存储空间不是算法过程中的瓶颈,我们设计的算法通常优先考虑时间复杂度。
本题也可以用空间换时间的思路来进行加速。
那么我们需要一种数据结构,它既可以保存数组中每个元素与其索引的关系,又可以快速的找到某个值的索引。很显然,可以用哈希表。在 java 中我们可以直接用 HashMap。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(nums.length); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int another = target - nums[i]; if (map.containsKey(another) && map.get(another) != i) { return new int[]{map.get(another), i}; } } return null; }
|
两遍循环,时间复杂度为 O(2n),省略常数后为 O(n);用到额外空间存储数组元素,空间复杂度为 O(n)。
一遍哈希表
时间复杂度已经为 O(n) 了,但是当 n 比较大的时候,这个常数还是会对算法造成一定的消耗。
其实,稍微换一下思路,只遍历一遍数组也能够完成。
在遍历数组时,除了将元素存入到哈希表中,还可以再回头来检查一下哈希表中是否已经存在当前元素所对应的目标元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(nums.length); for (int i = 0; i < nums.length; i++) { int another = target - nums[i]; if (map.containsKey(another)) { return new int[]{map.get(another), i}; } map.put(nums[i], i); } return null; }
|
一遍循环,时间复杂度为 O(n);用到额外空间存储数组元素,空间复杂度为 O(n)。
凑字数
这道题还是比较简单的,相信很多人刚开始刷 leetcode 就是从这道题开始,这篇文章就当是回顾一下思路吧。