Advanture 1 - leetcode 1 - Two Sum

leetcode解题思路总结:

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
链接:

示例:

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

对于这样的题目,最容易想到的是brute-force暴力解法, 直接两重循环进行迭代.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
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[j] == target-nums[i])
return new int[] {i, j};
}
}
// Returns null if solution not found.
return null;
}
}

复杂度分析(Complexity Analysising):

  • 时间复杂度(Time complexity): $O(n^2)$
  • 空间复杂度(Space complexity): $O(1)$

暴力解法虽然可行,但是时间复杂度为$O(n^2)$, 考虑进行优化,首先想到是可以以空间换时间:

如果能够把给定数组的数,用某种数据结构将每个数的数值以及对应的索引(index)保存起来,则只需要用一次遍历查找
target - nums[i]是否存在于该数据结构中,且非nums[i]即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}

for (int i = 0; i < nums.length; i++) {
int remain = target - map.get(nums[i]);
if (map.containsKey(remain) && map.get(remain) != i)
return new int[] {i, map.get(remain)};
}
// returns null if solution not found.
reutrn null;
}
}

复杂度分析(Complexity Analysising):

  • 时间复杂度(Time complexity): $O(n)$
  • 空间复杂度(Space complexity): $O(n)$

年轻的我,本以为上面的这种解法已经是最优的了,但是看完讨论区之后,才焕然大悟,它还可以进行优化:
仔细看的话,上面的HashMap算法访问了nums数组两遍,而接下来,从leetcode上学习到的优化方法就是nums数组的访问从两遍降到一遍.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int remain = target - nums[i];
if (map.containsKey(remain))
return new int[] {map.get(remain), i};
map.put(nums[i], i);
}
return null;
}
}

由于map中保存的肯定是索引i之前的数,因此不需要判断map.get(remain) != i.

复杂度分析(Complexity Analysising):

  • 时间复杂度(Time complexity): O(n)
  • 空间复杂度(Space complexity): O(n)

总结

对于能够快速使用brute-force暴力解法解决的问题,考虑优化时,首先考虑能够减少循环的嵌套,其次是考虑减少数组的访问次数、元素比较次数、元素交换次数等。

-------------The End Thanks for reading.-------------
Donate me, thanks for your support!