1、基础方法
思路:双层遍历数组,如果找到目标的target,退出双层循环
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int *result = (int *)malloc(2 * sizeof(int));
bool found = false;
for(int i = 0; i < numsSize - 1; i++){
if(!found){
for(int j = i + 1; j < numsSize; j++){
if(nums[i] + nums[j] == target){
result[0] = i;
result[1] = j;
found = true;
break;
}
}
}
}
if(found){
*returnSize = 2;
}
else{
*returnSize = 0;
}
return result;
}
2、字典方法
思路:
1、首先遍历数组确定nums的最大值max和最小值min;
2、创建字典map数组,用于快速定位目标值在nums数组中的索引 。map数组以数组下标为要找的目标元素,下标对应的值为该下标在nums数组中的下标位置,例如map[3] = 5,即在数组nums中,元素3在nums中的下标为5。数组大小为max - min + 1,目的是为了将max - min + 1 区间所有元素存入map,由于nums并不是从min-max连续的,所以map会有许多为空元素。为了防止map数组初始化的时候数组元素随机赋值,需要用到calloc函数,将map的元素值均初始化为0。
3、遍历nums数组,对于每一个数组元素nums[i],如果map中存在lookfornum = target - nums[i],则直接返回,如果不存在,则建立数组元素的地址映射,map[nums[i] - min] = i + 1(其中,索引存为i + 1,而不是存为i本身,原因为当遍历到数组最小值时,即nums[i] - min = 0时,无法区分该索引到底是min在原nums数组中下标就是0,还是因为map数组在calloc 函数初始化的时候为0)。
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int i, max, min;
max = min = nums[0];
for(i = 0; i < numsSize; i++) {
if(nums[i] > max) max = nums[i];
if(nums[i] < min) min = nums[i];
}
int *map = (int *)calloc((max - min + 1), sizeof(int));
int *result = (int *)malloc(2 * sizeof(int));
bool found = false;
for(i = 0; i < numsSize; i++) {
int lookfornum = target - nums[i];
if(lookfornum < min || lookfornum > max) continue;
int dis = lookfornum - min;
if (map[dis]) {
result[0] = i;
result[1] = map[dis] - 1;
found = true;
break;
}
else{
map[nums[i] - min] = i + 1;
}
}
if(found)
*returnSize = 2;
else
*returnSize= 0;
return result;
}
本系列文章,旨在打造LeetCode题目解题方法,帮助和引导同学们开阔学习算法思路,由于个人能力和精力的局限性,也会参考其他网站的代码和思路,如有侵权,请联系本人删除。
网友评论