leetcode 1 Two Sums
本帖最后由 Seawolf 于 2019-8-16 03:15 编辑暴力解法：
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
int i,j;
int[] array = {-1,-1};
for(i = 0 ; i < len-1; i++){
for(j = i+1; j < len ;j++){
if(nums + nums == target){
array = I;
array = j;
return array;
}
}
}
return null;
}
}
两个for loop，running time O(n^2)
引入hashmap 对算法进行改进：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
if(map.get(nums) != null) {
int res[] = {map.get(nums), I};
return res;
}
map.put(target - nums, i);
}
return new int[]{};
}
}
running time 提高到 O(n)
页:
[1]