Open zhuangjinxin opened 6 years ago
解法1:
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 };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
时间复杂度:O(n2) 空间复杂度:O(1)
解法2:
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 complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}
时间复杂度:O(n) 空间复杂度:O(n)
Hash把查找的时间复杂度从O(n)降低到O(1),但空间复杂度提高了;
解法3:
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
时间复杂度:O(n) 空间复杂度:O(n)
1.把解法2中两次循环合并; 2.map中只存在数组下标在i之前的元素,可以减少目标元素与i重复的判断;
public static int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i <= nums.length-1; i++) {
for (int j = i+1; j <= nums.length-1; j++) {
if (nums[i]+nums[j]==target){
result[0]=i;
result[1]=j;
return result;
}
}
}
return result;
}
对比了别人的写法,才知道自己的写法有多low~....
return new int[] {i,j}
更简洁)i<=nums.length-1
等价于i<nums.length
, 后者更简洁;
题目: Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example: