- Two Sum
Given an array of integers, returnindicesof the two numbers such that they add up to a specific target.
You may assume that each input would haveexactlyone solution, and you may not use thesameelement twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].
一、穷举法:
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result=new int[2]; //1
for (int i=0;i<nums.length-1;i++){
for(int j=nums.length-1;j>i;j--){ //2
if(nums[i]+nums[j]==target){
result[0]=i;
result[1]=j;
break;
}
}
}
return result;
}
throw new IllegalArgumentException("No two sum solution");//3
}
1、语法错误:int[] result=new int[];
数组必须指定大小,否则造成资源浪费。
2、逻辑错误:没有关注这里的j是作为数组下标存在的,因此出现了数组溢出和下标与实际的数字不吻合的错误。
3、逻辑错误:必须要时刻记住程序的运行的完整的情况,即JAVA中重要的异常处理问题。
二、双列数组法(空间换时间)
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result=new int[2];
Map<Integer,Integer> map = new HashMap();
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
result[0]=map.get(nums[i]);
result[1]=i;
}
else{
map.put(target-nums[i],i); //1
}
}
return result;
}
throw new IllegalArgumentException("No two sum solution");
}
1、逻辑错误:map.put(i,target-nums[i])
对于双列数组map[key,value],要分清楚什么是用于查找的关键字,什么是储存的值。目标一般是value,而不是key。
网友评论