1. 链接：1. 两数之和。

我对算法的学习要求和思路为： 1. 算法我认为脱胎于数学，先走数学公式，再写算法。 2. 每个算法要求做成函数的形式，方便将来使用。

编程导航

题目

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

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

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

数学建模

题目重述

  设一维数组的名称为 \(A\)，数组的元素个数为 \(n_A\)，其中 \(n_A \geq 2\)，元素分别为 \(a_0\)、\(a_1\)、···、\(a_{n-1}\)，且均为整数，并记为 \(a_i\)，其中 \(0 \leq i \leq (n_A - 1)\)，整数目标值为 \(b\)。取出的两个整数中，其中一个可以同记为 \(a_i\)，另外一个整数记为 \(a_j\)，其中 \(0 \leq j \leq (n_A - 1)\)，且 \(j \neq i\)，\(n_A\)、\(i\)、\(j\) 均为整数，若存在 \(i\) 和 \(j\)，使得 \(a_i + a_j = b\)，求 \(i\) 和 \(j\)的值。并表示为数组 \(C\)。

思路

  这个没有很深的公式了，直接写就好了。我们可以做差和 \(0\) 比较：

\[ b - a_i - a_j = 0 \]

接口

  数学公式符号和程序变量名称有自己的特点，不能要求保持一致，符号首要特点是可读性。数学符号是简短的，有上下标；而程序变量应该能望文生义，由英文单词或者缩写拼装而成。下表仅表示该算法对应的函数里的变量。

数学符号 取值范围 代码变量 说明
\(A\) - int* ArryInput 输入矩阵
\(n_A\) \(n_A \geq 2\) int arrySize 元素个数
\(b\) - int target 输入目标值
\(i\) \(0 \leq i \leq (n_A - 1)\) int i 第 \(i\) 个元素
\(j\) \(0 \leq j \leq (n_A - 1)\)、\(j \neq i\) int j 第 \(j\) 个元素
\(C\) - int* arryTwoSum 输出矩阵
\(n_C\) - int* returnSize 元素个数

算法代码

变量

函数名 数据类型 main twoSum arryTwoSum
说明 - 主函数 力扣 自定义
输入矩阵 int* nums nums ArryInput
元素个数 int numsSize numsSize arrySize
输入目标值 int target target target
输出矩阵 int* ans twoSum arryTwoSum
元素个数 int* returnSize returnSize returnSize

代码

C

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>

/// @brief 在数组中寻找两个数的和等于目标值
/// @param ArryInput    一维输入数组
/// @param arrySize     数组元素个数
/// @param target       目标值
/// @param returnSize   返回数组的元素个数
int* arryTwoSum(int* ArryInput, int arrySize, int target, int* returnSize);


/// @brief 在数组中寻找两个数的和等于目标值
/// @param nums         一维输入数组
/// @param numsSize     数组元素个数
/// @param target       目标值
/// @param returnSize   返回数组的元素个数
int* twoSum(int* nums, int numsSize, int target, int* returnSize);


/// @brief      主函数
/// @details    给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
/// 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
/// 你可以按任意顺序返回答案。
int main()
{
    // 输入
    int nums[] = { 0,1,2 }; // 给定一个一维数组
    int target = 3; // 目标值
    int numsSize = sizeof(nums) / sizeof(nums[0]); // 计算元素个数

    // 输出
    // 初始化
    int* ans = NULL, * ansCopy = NULL;
    int returnNum = 0;
    int* returnSize = &returnNum;

    // 计算
    ans = twoSum(nums, numsSize, target, returnSize);
    ansCopy = ans;

    // 打印
    char str[100] = "数组下标为：[";
    char temp[20] = { '\0' };
    for (int i = 0; i < returnNum; i = i + 1)
    {
        if (i == returnNum - 1)
        {
            sprintf(temp, "%d", *(ans + i));
        }
        else
        {
            sprintf(temp, "%d, ", *(ans + i));
        }
        strcat(str, temp);
    }
    strcat(str, "]");
    puts(str);

    // 清理
    returnNum = 0;
    returnSize = NULL;
    free(ansCopy);
    ans = NULL, ansCopy = NULL;

    return NULL;
}

// 拷贝到力扣要声明 arryTwoSum 函数
int* arryTwoSum(int* ArryInput, int arrySize, int target, int* returnSize);

/// @details    一维整数数组两元素求和等于目标值，返回两元素所在位置
/// @see        arryTwoSum
/// @note       这是需要在力扣里跑的，所以重新封装了函数名称和变量名
/// @warning    复制到力扣里时，需要重新在该函数前面声明 arryTwoSum 函数：int* arryTwoSum(int* ArryInput, int arrySize, int target, int* returnSize);
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    return arryTwoSum(nums, numsSize, target, returnSize);
}

/// @details 一维整数数组两元素求和等于目标值，返回两元素所在位置
/// @see twoSum
/// @note 这是不能直接在力扣里跑的，因为定义自己喜欢的函数名和变量名
int* arryTwoSum(int* ArryInput, int arrySize, int target, int* returnSize)
{
    // 匹配状态
    int State = 0;

    // 输出
    int i = 0;
    int j = 0;

    // 计算
    for (i = 0; i < arrySize; i = i + 1)
    {
        for (j = i + 1; j < arrySize; j = j + 1)
        {
            if (target - ArryInput[i] - ArryInput[j] == 0)
            {
                State = 1;
                break;
            }
        }
        if (State == 1)
        {
            break;
        }
    }

    // 返回数组下标
    int n = 2;
    int* ArryReturn = NULL, * ArryRetCopy = NULL;
    ArryReturn = (int*)malloc(sizeof(int) * n);
    ArryRetCopy = ArryReturn;
    if (ArryReturn != NULL)
    {
        // 赋值
        ArryReturn[0] = i; ArryReturn[1] = j;
        *returnSize = 2;
        return ArryRetCopy;
    }
    else
    {
        printf("malloc error!\n");
        exit(-1);
    }

    *returnSize = 0;
    return NULL;
}

C++

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
using namespace std;

unsigned int ArrayTwoSum (signed int *A, signed int b);

int main()
{
  //输入
  //矩阵
  signed int nums[] = {0,1,2};
  //目标值
  signed int target = 2;

  //输出
  cout << ArrayTwoSum (nums, target)<< endl;
}

//函数
//一维整数数组两元素求和等于目标值，返回两元素所在位置
unsigned int ArrayTwoSum (signed int *A, signed int b)
{
  //匹配状态
  unsigned int State = 0;

  //计算元素个数
  unsigned int n = sizeof(A)/sizeof(signed int);

  //输出
  unsigned int i = 0;
  unsigned int j = 0;

  //计算
  for (i = 0; i < n; i = i + 1)
  {
    for (j = i + 1; j < n; j = j + 1)
    {
      if(b - A[i] - A[j] == 0)
      {
        State = 1;
        break;
      }
    }
    if(State == 1)
      {
        break;
      }
  }

  //返回数组下标
  unsigned int C[2] = {i,j};
  return C;
}