【LeetCode】两数之和、大数相加

主页：HABUO🍁主页：HABUO

1.两数之和

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

• 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
• 你可以按任意顺序返回答案。

示例：

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

输入：nums = [3,2,4], target = 6 输出：[1,2]

输入：nums = [3,3], target = 6 输出：[0,1]

分析：以我们现在的知识水平，最容易想到的就是暴力枚举，因为我们之前写过冒泡排序，类比思想，固定一个数据不动遍历其它数据，如果和等于target返回这两个数据的下标，如果遍历完了，还没有那么，固定的那个数据+1，从而固定下一个数据，再进行遍历，这我们就能感受到，这个时间复杂度是不是O(N^2)，不太好，但知识水平有限，我们先这样做，随着学习的深入，之后我们再以优越的方法解决此题。整体思路见下图：

int* twoSum(int* nums, int numsSize, int target, int* returnSize) 
{
    int rest = 0;
    for(rest = 0; rest < numsSize;rest++)
    {
        //
        for(int move = rest + 1 ; move < numsSize; move++)
        {
            if(nums[rest]+nums[move] == target)
            {
                int* sz = (int*)malloc(2*sizeof(int));
                sz[0] = rest;
                sz[1] = move;
                *returnSize = 2;
                return sz;
            }   
        }
    }
    return NULL;
}

需要注意的是，题目中要求是返回两个数据的下标，我们都知道return只能返回一个值，那怎么办？很容易想到以一个数组去返回，函数中有一个参数是 int* returnSize，这个叫做输出型参数，什么意思呢？你看我们既然开辟了一个数组，函数外需要访问，但是不知道数组大小，难道一直访问下去吗？这肯定会导致越界，因此我们需要告诉函数外这个数组的大小是什么，returnSize就是完成这个事，你看它传的是地址，解引用就可以对外部这个数值进行修改，因此我们通过此来返回数组的大小。

2.大数相加

题目：整数的 数组形式  num 是按照从左到右的顺序表示其数字的数组。

• 例如，对于 num = 1321 ，数组形式是 [1,3,2,1] 。
• 给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。

示例：

输入：num = [1,2,0,0], k = 34    输出：[1,2,3,4]      解释：1200 + 34 = 1234

输入：num = [2,7,4], k = 181     输出：[4,5,5]         解释：274 + 181 = 455

输入：num = [2,1,5], k = 806     输出：[1,0,2,1]      解释：215 + 806 = 1021

分析：

首先我们应该想一下为什么会有这样的一种题，背景是什么？无论我们的int  unsigned int 就是long long 它们所能存储的数据是不是有限，那像我们导弹、航空航天的一些数据它可能相当巨大，这样的一个类型是不是不能存，所以有了数组存大数的这样一种形式。但万变不离其宗，你要计算数据，是不是要拿到每一位的数，对应位进行相加，这就是总的思想。所以每步分析见下：

第一步：题中要求返回的数据以数组形式，那我们首先要知道这个数组要设置多大吧，所以，我们先来分析这个结果数组，我们都知道3位数与3位数相加你最大也就是4位数，因此呢最终结果数组就是两组数中最大的数再多一位，所以我们应该要知道哪组数最大。

    //求k的位数
    int Ksize = 0;
    int Knum = k;
    while(knum)
    {
        Ksize++;
        Knum /= 10;
    }
    //求两组数位数最大
    int len =(numSize > Ksize ? numSize : Ksize);
    //建立结果数组
    int* retArr = (int*)malloc(sizeof((len+1)*int);

第二步：是不是就是进入一个循环，拿到两组数的每一位，然后相加，但这里需要考虑一些细节，我们算加法时，都是从最低位开始算起，再一个，需要考虑进位的问题，还有得到的结果怎么放到数组的一个问题，如果我们从后往前方这就存在假设最终没有进位，那我们是按照最大的再加一位进行建立的数组，那数组第一位是就空着了，当然用之前我们所学的顺序表的一些知识，可以往前挪，这就麻烦了，我们可以正着放，最终逆置一下就可以达到我们所想要的目的了。 整体思路见下图：

这里相应的产出一个问题，这是数组大，k数值小，那如果是k大，数组小呢？！是不是极有可能造成越界访问，因此需要解决这样的问题的话，进行如下操作，如果Ni还有值，我们就让n=num[Ni]，如果没有值了，自然也不会进入到if语句当中，我们直接对n定义为0即可。

int n = 0;
if (Ni >= 0)
{
    n = num[Ni];
}

进位的问题，我们用一个next值进行保存即可， 有进位就让next置1，没有进位就让它置0，需要注意没有进位的时候要主动置0，防止因为上一位的计算所保留的进位，影响到该位的计算。具体思想见下：

int ret = n + k % 10 + next;
if (ret > 9)
{
    next = 1;
    retArr[Ai] = ret - 10;
    Ai++;
}
else
{
    next = 0;
    retArr[Ai] = ret;
    Ai++;
}

当计算走到最后的时候，又会出现一个问题，即len已经减到0了，但是我们如果还有一位进位，那么循环进入不进去，那这个进位就不会放到数组当中，就会导致丢失一个最高位1的 情况，怎么解决呢？思想就是在最后一步如果产生进位，主动的把进位补上即可，思想见下：

if (len == 0 && ret > 9)
{
    retArr[Ai] = next;
    retSize = retSize + 1;
}

所以计算部分整体思路见下：

int Ni = numSize - 1;
int Ai = 0;
int next = 0;
while (len--)
{
    //处理k大数组小，导致数组越界访问的情况
    int n = 0;
    if (Ni >= 0)
    {
        n = num[Ni];
    }
    int ret = n + k % 10 + next;
    Ni--;
    k /= 10;
    if (ret > 9)
    {
        next = 1;
        retArr[Ai] = ret - 10;
        Ai++;
    }
    else
    {
        next = 0;
        retArr[Ai] = ret;
        Ai++;
    }
    //处理最后一步有进位的情况
    if (len == 0 && ret > 9)
    {
        retArr[Ai] = next;
        retSize = retSize + 1;
    }
}

前面提到我们在建立新的数组中放置数据是正着放的，这不是我们所想要的计算结果，我们需要对数组进行逆置，逆置就相对比较简单，只需要建立left，right两个标记进行来回赋值即可

//逆置结果数组
int left = 0;
int right = retSize - 1;
while (left < right)
{
    int temp = retArr[left];
    retArr[left] = retArr[right];
    retArr[right] = temp;
    left++;
    right--;
}

总代码见下：

int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
    //求k的位数
    int Ksize = 0;
    int Knum = k;
    while (Knum)
    {
        Ksize++;
        Knum /= 10;
    }
    //求两组数位数最大
    int len = (numSize > Ksize ? numSize : Ksize);
    //建立结果数组
    int* retArr = (int*)malloc(sizeof(int) * (len + 1));
    int retSize = len;//结果数组大小
    //计算过程
    int Ni = numSize - 1;
    int Ai = 0;
    int next = 0;
    while (len--)
    {
        //处理k大数组小，导致数组越界访问的情况
        int n = 0;
        if (Ni >= 0)
        {
            n = num[Ni];
        }
        int ret = n + k % 10 + next;
        Ni--;
        k /= 10;
        if (ret > 9)
        {
            next = 1;
            retArr[Ai] = ret - 10;
            Ai++;
        }
        else
        {
            next = 0;
            retArr[Ai] = ret;
            Ai++;
        }
        //处理最后一步有进位的情况
        if (len == 0 && ret > 9)
        {
            retArr[Ai] = next;
            retSize = retSize + 1;
        }
    }
    //逆置结果数组
    int left = 0;
    int right = retSize - 1;
    while (left < right)
    {
        int temp = retArr[left];
        retArr[left] = retArr[right];
        retArr[right] = temp;
        left++;
        right--;
    }
    *returnSize = retSize;//返回数组大小
    return retArr;//返回数组
}