给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解1:穷举法，时间复杂度o(n^2)
public int[] twoSum(int[] nums, int target) {
int indices[] = new int[2];
for(int i = 0; i < nums.length - 1; i++){
for(int j = i+1; j < nums.length; j++){
if((i < j) && (nums[i] + nums[j] == target)){
indices[0] = i;
indices[1] = j;
break;
}
}
}
return indices;
}
解2:排序后,类似进行快速排序一次排序，时间复杂度o(2n)
public int[] twoSum(int[] nums, int target) {
//浅复制，拷贝副本
int[] copynums = new int[nums.length];
System.arraycopy(nums, 0, copynums, 0, nums.length);
Arrays.sort(nums);
//
int indices[] = new int[2];
int start = 0;
int end = nums.length - 1;
int a = 0;
int b = 0;
while (start < end) {
int sum = nums[start] + nums[end];
if (sum < target) {
start++;
} else if (sum > target) {
end--;
} else if (sum == target) {
a = nums[start];
b = nums[end];
break;
}
}
for (int i = 0; i < copynums.length; i++) {
if (a == copynums[i]) {
indices[0] = i;
} else if (b == copynums[i]) {
indices[1] = i;
}
}
return indices;
}
解3：空间换时间，时间复杂度o(n)
public int[] twoSum(int[] nums, int target) {
int indices[] = new int[2];
Map<Integer,Integer> tmpMap = new HashMap();
for(int i = 0; i < nums.length; i++){
if(tmpMap.containsKey(nums[i])){
indices[0]=tmpMap.get(nums[i]);
indices[1]=i;
break;
}else{
tmpMap.put(target-nums[i],i);
}
}
return indices;
}
