LeetCode 相关的文章：

1. LeetCode | 206.反转链表
2. LeetCode | 24.两两交换链表中的节点
3. LeetCode | 141.环形链表
4. LeetCode | 20.有效的括号
5. LeetCode | 225.用队列实现栈
6. LeetCode | 232.用栈实现队列
7. LeetCode | 703.数据流中的第K大元素

这次来写一下 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)。这就是典型的通过 空间换时间 和 时间换空间 的情况。