总感觉直接在LeetCode上直接写完代码（实际是啥也不会、抄袭别人），自己不完全能留下一些印象，所以我想起这个Post记录一下。由于我没事会翻自己的网站看，所以应该还能起到复习的效果吧（？）

两数之和

两数之和题目大致是从数组中找出两个两个数，这两个数的和正好等于目标数。

大致有两种解法：

  1. 遍历。拿一个数，与剩余其他的数做加法，看是否等于目标数。

  2. 按照我自己的理解说法，就是将看过的数留下记忆，再将新拿到的数与目标数做差，看差值是否与自己心中的数一致。

    记忆工具用的是hash表。因为有记忆了，所以算法的时间复杂度应该会下降。（我对算法理性理解很差，所以请饶了我吧）

题目

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) {
    
}

我还是对C和C++感情深一些，python这种没有数据类型的编程语言着实让我有时很困扰。所以我还是记录以C为主的代码解决方案。

解法一

这个我能自己写个大概，所以先自己尝试完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
  int* returnnums = malloc(2 * sizeof(int));
  for (int i = 0; i < numsSize; i ++) {
      for (int j = 0; j < numsSize; j ++) {
        if ((nums[i] + nums[j]) == target && i != j){
          returnnums[0] = i;
          returnnums[1] = j;
          *returnSize = 2;
          return returnnums;
        }
      }
    }
  *returnSize = 0;
  return NULL;
}

总结

整理一下我自己第一遍写出现的一些问题：

  1. 不知道应该return什么
  2. 不知道returnSize是干什么的，为什么要有他
  3. 只在if语句中return了，没有注意到if语句外也需要return
  4. 忘记条件不能同时取两个相同的数。

解法二

我对Hash表的使用不熟悉，要么搜索引擎解决，要么看别人的解决方案，或者找到合适的文档解决。

对于第一次使用Hash表，我计划先学习别人的解决方案，之后再对应查找相关文档。

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) {
    
}