[数据结构与算法]LeetCode01两数之和

最近想换工作了，作为菜鸡一枚，特此记录一下面试的准备和刷题记录，还希望有大佬能及时指出文章中的问题，在此先谢谢各位哥哥姐姐了！！！

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

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

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

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、最先想到的是暴力解法：

该算法的时间复杂度为O(n^2)：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
	int i = 0, j = 0;
	int* retbuf = (int*)malloc(sizeof(int)*2);
	for (i = 0; i < numsSize-1; ++i)
	{
		for (j = i + 1; j < numsSize; ++j)
		{
			if (target == nums[i] + nums[j])
			{
				if (retbuf != NULL) {
					*retbuf = i;
					*(retbuf + 1) = j;
					*returnSize = 2;
					return retbuf;
				}
			}
		}
	}
	*returnSize = 0;
	return NULL;
}

?Note: The returned array must be malloced, assume caller calls free().

这句话的意思是，返回的数组一定要被动态分配内存，假设调用者call free()函数。

注意这里一定要写对SIZE！！！记得判断申请内存是否成功。

延伸知识：

malloc用法：

void* malloc(size_t size);

malloc向系统申请分配制定size个字节的内存空间。返回类型是void*类型。在C或者C++中，void*类型可以强制转换为任何其他类型的指针。

int* retbuf = (int*)malloc(sizeof(int)*2);? <==>? int retbuf[2];

使用完记得free( retbuf );

	int* p = twoSum(num, 4, 9, &size);
	printf("p0 %d p1 %d\n", p[0], p[1]);
	free(p);

一定不能写? int* retbuf = (int*)malloc(2);这不是new运算符。这里有一点不是很明白，希望有大佬解释一下：

这种写法?int* retbuf = (int*)malloc(2);? ?如果我在main函数中不去free(p),?在visual studio可以正常运行（功能也正常）。如果调用free(p),程序将会崩溃。不是说堆区的数据不手动释放，会被系统自动回收吗？回收的时候不会崩溃吗？

如果是c++代码可以用new delete。

int* retbuf = new int[2];? <==>? int retbuf[2];

注意是[]，不是()；int* p= new int(2)? <==>? int temp =2； int *p =&temp;

使用完记得delete [] retbuf;

malloc()是函数，这里的new()是运算符，不能重载。

二、哈希表查找法：

a 和b的值存在一定的固定关系，即 a = target - b，因此可以采用哈希表查找法。

默认将数组的第一个元素存入哈希表中，然后依次从1遍历到len；

若target - num[i] 不在哈希表中，则插入新的数据和下标。

若target - num[i]? 在哈希表中，则说明当前的值（num[i] ）和之前的值（target - num[i]? ）满足条件，返回即可。

这种方法只需要遍历一遍数组即可，时间复杂度为O(n)。

代码如下：

    vector<int> twoSum(vector<int>& nums, int target) {
	int len = nums.size();
	map<int, int> mymap;
	
	vector<int> ret(2,0);
	for (int i = 0; i < len; i++)
	{
		if (mymap.count(target - nums[i]) > 0)//success
		{
			ret[0] = i;
			ret[1] = mymap[target - nums[i]];
			return ret;
		}
		else
		{
			mymap[nums[i]] = i;
		}
	}
    return ret;
    }