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.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
我的答案：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target) {
for(int i=0; i<numsSize; i++){
for(int j=i+1;j<numsSize; j++){
if(nums[i]+nums[j]==target){
int *result = (int *)malloc(sizeof(int)*2);
result[0] = i;
result[1] = j;
return result;
}
}
}
return NULL;
}
性能：
时间复杂度：O(n2)
runtime:89ms
beats 76.01% submissions
网上优秀答案：
int* twoSum(int* nums, int numsSize, int target) {
int array[100000] = {-1};
int temp = 0;
int i = 0;
static int result[2];
for(i = 0; i < numsSize; i++) {
array[nums[i] + 5000] = i;
}
for(i = 0; i < numsSize; i++) {
temp = array[target - nums[i] + 5000];
if(temp)
if(temp > i) {
result[0] = i;
result[1] = temp;
break;
}
}
return result;
}
性能：
时间复杂度：O(n)
runtime:3ms
beats 94.38% submissions
牺牲空间复杂度换取时间复杂度
Java、C++ 有现成的HashMap
