【LeetCode】每日一题&&两数之和&&寻找正序数组的中位数&&找出字符串中第一个匹配项的下标&&在排序数组中查找元素的第一个和最后一个位置

=========================================================================

主页点击直达：个人主页

我的小仓库：代码仓库

C语言偷着笑：C语言专栏

数据结构挨打小记：初阶数据结构专栏

Linux被操作记：Linux专栏

LeetCode刷题掉发记：LeetCode刷题

算法：算法专栏 

C++头疼记：C++专栏

计算机网络基础：网络专栏=========================================================================

目录

LeetCode 1.两数之和

LeetCode 4.寻找正序数组的中位数

LeetCode 28.找出字符串中第一个匹配项的下标

 LeetCode 34.在排序数组中查找元素的第一个位置和最后一个位置

---

LeetCode 1.两数之和

难度：简单

OJ链接

题目描述：

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

思路讲解：双指针暴力遍历求解

第一篇文章我们说到有关数组的题我们要优先考虑双/多指针，这道题目也不例外。定义两个指针，一个在前一个在后，前一个遍历数组看和后一个的值相加匹不匹配，如果不匹配两个指针都向后加加知道，遍历出结果。因为题目中明确规定只有两个数，因此我们只开辟两个空间大小的数组，遍历出结果将两个指针的值放在我们开辟的数组中，返回我们的数组即可。

实现代码

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *a=(int *)malloc(sizeof(int)*2);
    for(int i=0;i<numsSize;i++)
    {
        for(int j=i+1;j<numsSize;j++)
        {
            if(nums[i]+nums[j]==target)
            {
                a[0]=i;
                 a[1]=j;
                break;
            }
        }
    }
   *returnSize=2;
   return a;
}

---

LeetCode 4.寻找正序数组的中位数

难度：困难

OJ链接

题目描述：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

思路讲解：双指针暴力合并

首先使用两个指针分别指向，两个数组的头，两两比较配合移动，将小的放在新开辟的数组中。然后判断新数组的大小的奇偶数，如果是奇数直接返回中间值，如果是偶数需要返回中间两数之和的平均数。

注意：

1.有可能一个数组走完了，另一个数组还没走完，哪一个我们也缺定不了，我们需要分别判断指针和两个数组距离的关系，将没移动完的数组全部放到新数组中。

2.有可能两个数组都为0，特殊情况我们要判断

3.数组总大小为偶数取平均数时，一定要除以浮点数。因为整数和整数相除只能得到整浮点数。

实现代码

 
 
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int begin1 = 0;
    int begin2 = 0;
    int* a = (int*)malloc(sizeof(int) * (nums1Size + nums2Size));
    if (a == NULL)
    {
        perror("malloc fail");
    }
    int i = 0;
    double b = 0;
    //根据大小合并两个数组
    while (begin1 < nums1Size && begin2 < nums2Size)
    {
        if (nums1[begin1] <= nums2[begin2])
        {
            a[i] = nums1[begin1];
            begin1++;
            i++;
        }
        else
        {
            a[i] = nums2[begin2];
            begin2++;
            i++;
        }
    }
    //判断数组是否合并完全
   while (begin1 <nums1Size)
    {
        a[i] = nums1[begin1];
        begin1++;
        i++;
    }
    while (begin2 < nums2Size)
    {
        a[i] = nums2[begin2];
        i++;
        begin2++;
    }
    //全为0的特殊情况
    if (a[nums1Size + nums2Size - 1] == 0)
    {
        return b;
    }
    //偶数个数
    else if ((nums1Size + nums2Size) % 2 == 0)
    {
      b=(a[(nums1Size+nums2Size)/2]+a[(nums1Size+nums2Size)/2-1])/(double)2;//强制类型转化
      return b;
    }
    else
    {
        //奇数个数
        b = a[(nums1Size + nums2Size) / 2];
        return b;
    }
}

---

LeetCode 28.找出字符串中第一个匹配项的下标

难度：简单

OJ链接

题目描述：相当于模拟实现strstr库函数

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

思路讲解：暴力双指针遍历求解

将两个指针分别指向两个数组，向后依次移动判断是否匹配，如果不匹配第一个数组的指针归于数组的第二个元素，第二个指针归于指针头，重新判断。当第一个指针移动到第一个数组长度减去第二个数组长度+1时，后面的就不必判断了。加一是为了防止两个数组的元素个数都为1。

实现代码

int strStr(char * haystack, char * needle){
    int next=0;
    int next2=0;
    int len1=strlen(haystack);
    int len2=strlen(needle);
    for(int i=0;i<len1-len2;i++)
    {
        next=i;
        next2=0;
        for(int j=0;j<len2+1;j++)
        {
    
            if(haystack[next]==needle[next2])
            {
                next++;
                next2++;
                if(len2==next2)
                {
                    return i;
                }
            }
            else
            {
                break;
            }
        }
    }
    return -1;
}

ps：这道题我的解法通过时间击败了LeetCode的100%的用户，希望大家能写出比我更快的代码！！！

---

LeetCode 34.在排序数组中查找元素的第一个位置和最后一个位置

难度：中等

OJ链接

题目描述：

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

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

思路讲解：双指针暴力遍历求解

先定义一个指针找到和目标值相等的位置，在定义一个指针从这个位置找和目标值不等的位置，后一个指针减一就是这个范围。

注意：

1.如果后一个指针走到最后一个位置都没有找到那么后一个这个范围就是第一个指针的位置到数组大小减一的位置

2.如果两个指针的值都没有改变则表示这个数组中没有这个目标值

3.如果只有数组只有一个值，直接判断是否和目标值相等，相等的话返回[0,0]区间，不相等返回[-1,-1]。

实现代码

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int *a=(int *)malloc(sizeof(int)*2);
    a[0]=a[1]=-1;
    int i=0;
    if(1==numsSize)
    {
        if(nums[0]==target)
        a[0]=a[1]=0;
        return a;
    }
    for( i=0;i<numsSize;i++)
    {
        if(nums[i]==target)
        {
            a[0]=i;
            break;
        }
    }
    for(int j=i;j<numsSize;j++)
    {
        if(nums[j]!=target)
        {
            a[1]=j-1;
            break;
        }
        if(j==numsSize-1)
    {
        a[1]=numsSize-1;
    }
    }
 
    if(a[0]==-1)
    {
        return a;
    }
    *returnSize=2;
    return a;
}

总结：第一篇文章我提到数组的问题可以用双指针/多指针的问题来解决，今天分享的这四道题目也基本都用到了双指针或者双指针的思想，如果有更好的解法可以在评论区交流。

以后每天我会在LeetCode上面练习一道随机题目，每一周给大家总结发出来，分享我的方法思路希望大家看完后有收获。