LeetCode | 1.两数之和
这次来写一下 LeetCode 的第 1 题，两数之和。
题目描述
题目直接从 LeetCode 上截图过来，题目如下：
上面的题就是 两数之和 题目的截图，同时 LeetCode 会根据选择的语言给出了一个类的定义或者函数的定义，然后在其中实现 两数之和 的解题过程。这次我分别使用 C 语言和 C++ 语言来进行完成。
C ++ 给出的类定义如下：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
}
};C++ 类中的 twoSum 成员函数有两个参数，分别是 nums 和 target，这两个参数和题目中描述的是一样的。
C 语言给出的函数定义如下：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
}C 语言给出的 twoSum 函数有四个参数，nums 和 target 和 C++ 是相同的，numsSize 表示数组 nums 的元素个数，而 returnSize 表示返回元素的个数。
问题分析
本题最简单的解法就是使用 双重循环 来找满足条件的两个数即可，即在 nums 中找出两个数进行相加，相加的和等于 target。这个是最直观的解题方法。这个方法我打算使用 C 语言去进行实现。
除了使用双重循环来找满足条件的两个数以外，还可以通过一个循环来完成。一个循环想要完成，就要建立一个 map 来记录已经遍历过的数据，map 的 key 为 nums 中的值，map 的 value 为 nums 的下标。比如，题目中的 [2, 7, 11, 15] 数组，然后记录到 map 中为 map[2] = 0，map[7] = 1 这样的形式，2 是 nums 中的值， 0 是 数值 2 的下标。然后循环使用 target 去减 nums[i]， 使用所得的结果，在 map 中进行 key 的查找，如果找到，直接返回当前的 nums 的下标 i，和在 map 中找到的 key 的 value 即可。以题目中的示例举例，target 为 9，当前 nums[1] = 7，9 - 7 的结果为 2，然后使用 2 做为 key 在 map 中查找，找到 map[2] 为 0，则将 0 （0 是 map[2] 的 value） 和 1 （1 是 nums[1] 的下标） 返回即可。
代码实现
C 语言的代码如下：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int i, j;
int *pArr = NULL;
for (i = 0; i < numsSize - 1; i ++) {
for (j = i + 1; j < numsSize; j ++ ) {
if (nums[i] + nums[j] == target) {
pArr = (int*)malloc(2 * sizeof(int));
pArr[0] = i;
pArr[1] = j;
*returnSize = 2;
return pArr;
}
}
}
return pArr;
}C++ 的代码如下：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> mapNums;
vector<int> arr;
int size = nums.size();
for(int i = 0; i < size; i ++)
{
map<int, int>::iterator iter = mapNums.find(target - nums[i]);
if (iter != mapNums.end())
{
arr.push_back(iter->second);
arr.push_back(i);
return arr;
}
mapNums[nums[i]] = i;
}
return arr;
}
};提交结果
在写完代码后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们可以根据给出的测试用例来继续修改代码。我们分别提交一次 C 语言的代码，然后再提交一次 C ++ 的代码，然后观察其输出的结果，以上两段代码 “提交” 以后的截图如下：
C 语言提交的结果如下：
C ++ 提交的结果如下：
观察两个程序的输出结果，使用 C 语言的执行时间要比使用 C++ 的执行时间长一些，因为在 C 语言中使用了两重循环，它的时间复杂度为 O(n^2)，而在 C++ 中只使用了单个循环，它的时间复杂度为 O(n)。而 C++ 代码的内存消耗比 C 语言的内存消耗要大，因为我们使用 map 来记录了 nums 中的值，它的空间复杂度为 O(n)。这就是典型的通过 空间换时间 和 时间换空间 的情况。