1、两数之和

发表于 分类于 ， ， 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟
简介：LeetCode第1题：两数之和 ； 学习计划 - 数据结构 - 第二天 - 数组

题目

【学习计划 - 数据结构 - 第二天 - 数组】https://leetcode-cn.com/study-plan/data-structures/

https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

程序样例

1
2
3
4
5
6
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){

}

我的解答

关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
//	returnSize不是返回值，意思是返回的元素的个数。这里手动设置为2 
	*returnSize = 2; 
	int* res= (int *)malloc(sizeof(int)*2);
	for(int i=0;i<numsSize;i++){
		for(int j=i+1;j<numsSize;j++){
			if(*(nums+i)+*(nums+j)==target){
				*(res)=i;
				*(res+1)=j;
				return res;
			}
		}
	} 
	return res;
}

思路：从第一个到最后一个，和后面的数相比较，如果相加为目标值，返回下标。

坑：

returnSize不是返回值，意思是返回的元素的个数。这里手动设置为2

测试的时候，需要在main函数中先为returnSize申请好地址。

参考：https://blog.csdn.net/weixin_38132153/article/details/103826835

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <stdlib.h>

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
//	returnSize不是返回值，意思是返回的元素的个数。这里手动设置为2 
	*returnSize = 2; 
	int* res= (int *)malloc(sizeof(int)*2);
	for(int i=0;i<numsSize;i++){
		for(int j=i+1;j<numsSize;j++){
			if(*(nums+i)+*(nums+j)==target){
				*(res)=i;
				*(res+1)=j;
				return res;
			}
		}
	} 
	return res;
}

main(){
	int numsSize=5,target=3;
	int nums[]={1,5,-2,-4,0};
	
	int* returnSize = (int *)malloc(sizeof(int));
	int *res;
	
	res = twoSum(nums,numsSize,target, returnSize);
	
	printf("--%d  %d--\n",res[0],res[1]);
}

复杂度分析

执行用时：80 ms, 在所有 C 提交中击败了72.45%的用户

内存消耗：6.2 MB, 在所有 C 提交中击败了68.54%的用户