@TOC

一、448. 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]

输出：[5,6]

示例 2：

输入：nums = [1,1]

输出：[2]

1.完整过程动态展示

以 输入：nums = [4,3,2,7,8,2,3,1]

  输出：[5,6]  为例

在这里插入图片描述

2.代码实现

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
    int* ptr = (int*)malloc(sizeof(int) * numsSize);
    int index = 0;
    int noindex = 0;
    while (index < numsSize)
    {
        if (nums[index] == index + 1)//判断是否与下标+1相等
        {
            index++;
        }
        else
        {
            noindex = nums[index] - 1;
            if (nums[noindex] == nums[index])//如果当前下标的数与
            //与对应位置的数相等
            {
                index++;
                continue;
            }
            int tmp = nums[noindex];//不相等就交换
            nums[noindex] = nums[index];
            nums[index] = tmp;
        }
    }
    int i = 0;
    int n = 0;
    for (i = 0; i < numsSize; i++)
    {
      if (nums[i] != i + 1)
        {
            ptr[n] = i + 1;
            n++;
        }
    }
    *returnSize = n;
    return ptr;
}

3.思路分析

1. 本题说明了所有值都在[1,n]的范围内，所以可以得到
   在这里插入图片描述

2.首先判断下标所对应的数是否等于下标+1

若等于 ，则index++，

在这里插入图片描述  

若不等于则将此时下标对应的数-1看作另一个的下标

比较两个数 ，若相等，则index++

在这里插入图片描述  

若不相等则交换

在这里插入图片描述  

二、238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]

输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]

输出: [0,0,9,0,0]

1.代码实现

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    int i=0;
    int*ptr=(int*)malloc(sizeof(int)*(numsSize));
    int left[numsSize];
    int right[numsSize];
    left[0]=1;//默认左缀之和的第一个数为1
    for(i=1;i<numsSize;i++)//左缀之和
    {
        left[i]=left[i-1]*nums[i-1];
    }
    right[numsSize-1]=1;//默认右缀之和的右边第一个数为1
    for(i=numsSize-2;i>=0;i--)//右缀之和
    {
        right[i]=right[i+1]*nums[i+1];
    }
    int index=0;
    for(i=0;i<numsSize;i++)//将左右缀之和相乘 
    {
        ptr[index]=left[i]*right[i];
        index++;
    }
    *returnSize=index;
    return ptr;
}

2. 过程

以 1  2  3   4 为例

1. 左缀之和
   在这里插入图片描述

设定一个left数组，用来记录原数组中每个下标所对应的左缀之和

而第一个数不存在左缀的，所以默认为1，所以从左边第二个数开始

left[i]=left[i-1] *  nums[i-1]

在这里插入图片描述  

2.右缀之和

在这里插入图片描述  

设定一个right数组，用来记录原数组中每个下标所对应的右缀之和

从右向左，右边第一个数不存在右缀之和，所以默认为1

从右边第二个数开始

right[i]=right[i+1] * nums[i+1]

在这里插入图片描述  

3.

最后分别将left与right每个下标的数相乘

ptr[i]=left[i] * right[i]

在这里插入图片描述