0%

刷算法(1)-两数之和

1. 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

第一种做法:暴力破解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package com.yangq.test;

public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] results = new int[] {0, 0};
for (int i =0; i < nums.length; i++) {
for (int j = i+1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
results[0] = i;
results[1] = j;
}
}

}
return results;
}
}

时间复杂度:O(n^2),空间复杂度O(1)。

第二种做法:一遍哈希

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

for (int i = 0; i< nums.length; i++) {
int diff = target - nums[i];
if (data.containsKey(diff)) {
return new int[] {i, data.get(diff)};
}
data.put(nums[i], i);
}
throw new IllegalArgumentException("can't found");
}
}
  • 时间复杂度:O(n),我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)的时间。

  • 空间复杂度:O(n),所需的额外空间取决于哈希表中存储的元素数量,该表最多需要存储 n个元素。