[Leetcode][1. 两数之和] 2种方法:暴力 和 HashMap

By Long Luo

Leetcode 1. 两数之和 题解。

方法一:暴力枚举

思路及算法:

最容易想到的方法是使用两层循环,第一层循环枚举数组中的每一个数xx,下一层循环在xx之后的元素中寻找数组中是否存在targetxtarget - 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)O(N^2),其中NN是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

  • 空间复杂度:O(1)O(1)

方法二:哈希表

思路及算法:

方法一的时间复杂度较高的原因是寻找targetxtarget - x的时间复杂度过高。因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。

使用HashMap,可以将寻找targetxtarget - x的时间复杂度降低到从O(N)O(N)降低到O(1)O(1)

这样我们创建一个哈希表,对于每一个xx,我们首先查询哈希表中是否存在targetxtarget - x,然后将xx插入到Map中,即可保证不会让xx和自己匹配。

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)O(N),其中NN是数组中的元素数量。对于每一个元素xx,我们可以O(1)O(1)地寻找targetxtarget - x

  • 空间复杂度:O(N)O(N),其中NN是数组中的元素数量。主要为哈希表的开销。


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. 😉😃💗