By Long Luo
1. 两数之和 题解。
方法一:暴力枚举
思路及算法:
最容易想到的方法是使用两层循环,第一层循环枚举数组中的每一个数 x,下一层循环在 x 之后的元素中寻找数组中是否存在 target−x。
1 2 3 4 5 6 7 8 9 10 11 12
| public int[] twoSum(int[] nums, int target) { int n = nums.length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[0]; } }
|
复杂度分析
- 时间复杂度:O(N2),其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
- 空间复杂度:O(1)。
方法二:哈希表
思路及算法:
方法一的时间复杂度较高的原因是寻找 target−x 的时间复杂度过高。因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。
使用 HashMap,可以将寻找 target−x 的时间复杂度降低到从 O(N) 降低到 O(1)。
这样我们创建一个哈希表,对于每一个x,我们首先查询哈希表中是否存在 target−x,然后将 x 插入到 HashMap 中,即可保证不会让 x 和自己匹配。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| public static int[] twoSum(int[] nums, int target) { int[] ans = new int[2]; int n = nums.length; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { if (map.containsKey(target - nums[i])) { ans[0] = i; ans[1] = map.get(target - nums[i]); return ans; } map.putIfAbsent(nums[i], i); }
return ans; }
|
复杂度分析
- 时间复杂度:O(N),其中 N 是数组中的元素数量。对于每一个元素 x,我们可以 O(1) 地寻找 target−x。
- 空间复杂度:O(N),其中 N 是数组中的元素数量。主要为哈希表的开销。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗