首页 > 其他分享 >LeetCode题集-1- 两数之和

LeetCode题集-1- 两数之和

时间:2024-08-31 08:57:32浏览次数:12  
标签:target nums int 复杂度 题集 循环 var LeetCode 两数

 

 

这个题目是什么意思呢?简单来说就是在一个数组中找出两个元素,使其和为我们设定的值,并且每个元素只能用一次。

 

如下图具体示例:

 

到这里不知道你是否已经有解题思路了呢?

解法一:双层循环

我第一反应就是双层循环,直接暴力破解。因为题目要求每个元素只能使用一次,并且已经计算过的也没必要再次计算,因此内层循环索引起始可以以外层索引+1作为起始点,具体代码如下:

public static int[] TwoSumForFor(int[] nums, int target)
{
    for (var i = 0; i < nums.Length; i++)
    {
        for (var j = i + 1; j < nums.Length; j++)
        {
            if (nums[i] + nums[j] == target)
            {
                return [i, j];
            }
        }
    }
    return [];
}

我们直接验证一下,通过了:

 

因为是双层循环因此算法时间复杂度是:O(N2),因为没有引用额外的空间因此空间复杂度是:O(1)。

:上面的[] ,[i, j]是C#12版本新增功能,是数组简洁表达语法。

解法二:双层循环+左右开弓

如果想在双层循环基础上继续优化算法要怎么办?

我们就按正常思维逻辑来梳理一下双层循环干了什么,外层循环:表示第一个加数,并且从第一个数到最后一个数循环一遍;内层循环:表示第二个加数,其作用就是使第一个加数按从前到后的顺序和其后面的每一个数加一遍。既然如此那能不能从前往后计算的同时也从后往前计算呢?显然使可以的,代码如下:

public static int[] TwoSumForForBidirectional(int[] nums, int target)
{
    for (var i = 0; i < nums.Length; i++)
    {
        var front = nums[i];
        var backIndex = nums.Length - 1 - i;
        var back = nums[backIndex];
        for (var j = i + 1; j < nums.Length; j++)
        {
            if (front + nums[j] == target)
            {
                return [i, j];
            }
            if (back + nums[j - 1] == target)
            {
                return [j - 1, backIndex];
            }
        }
    }
    return [];
}

运行结果如下:

 

理想情况下可能会提升一倍的效率,但是细心的朋友应该发现,平台上的运行结果,比双层循环还长了3ms,不过感觉这个平台结果不是很准,下面我们用基准测试,对两个方法进行测试,我们随机构建长度为2000的数组,并把目标数随机放到不同位置,测试10000次。

 

从基准测试的结果来看,整体上并没有提升多少性能。这是因为这个算法本质上时间复杂度还是:O(N2),因此并没有真正起到优化的作用,只有特定的数据分别可能才会有相对较好的表现,这个算法就当作给我们提供了一种解题思路吧。

解法三:单层循环+LastIndexOf

既然左右开弓不行,我们换一个思路,想办法去掉一层循环。

首先外层循环需要保留,因为需要把每个元素都计算一遍,因此我们从内层循环下手。想想题目,是要找到两个数使其和为目标值,那么我们是否可以在循环第一个数时候,通过目标值计算出我们要找的第二个值,看看这个值是否存在,如果存在,则完成算法,否则继续循环直到找到为止。按照这个思路我立马想到C#里的IndexOf和LastIndexOf方法,直接上代码:

  public static int[] TwoSumForLastIndexOf(int[] nums, int target)
  {
      for (var i = 0; i < nums.Length; i++)
      {
          var j = Array.LastIndexOf(nums, target - nums[i], nums.Length - 1, nums.Length - 1 - i);
          if (j >= 0 && j != i)
          {
              return [i, j];
          }
      }
      return [];
  }

运行结果如下:

 

:Array.LastIndexOf<T>(T[] array, T value, int startIndex, int count)方法可以指定从什么地方开始查找,查找多少个数。

同样我们再做一次基准测试做对比。

 

可以发现这一版本算法性能大幅提升,但是我们细想一下,LastIndexOf方法本质还是在数组中找一个元素,最坏的情况还是要把整个数组遍历一遍,只能说C#本身做了很好的优化使其性能很高,但是从算法时间复杂度的角度来看,其仍然是 O(N) 的,也就是说这一版本算法时间复杂度还是O(N2)。

解法四:单层循环+字典(哈希)

哪到底如何才能把O(N)的集合查找时间复杂度优化了呢?如果能改造到O(1) 就好了,顺着这个思路还真想到了一种数据结构-哈希表,可以做到O(1) 的查找时间复杂度。

在C#中可以使用Dictionary字典类型,数据结构选好了,下面就是怎么用的问题,key存什么?value存什么?

再次回忆一下题目要求,是找到两个数使其和为目标值,假设x+y=target,x为第一个数,并且外层循环第一个数,那么当处理数据x时,同时能得到y=target-x,如果数组中后面存在值为y的元素,是不是就意味着这对[x,y]就是我们要找的值,因此我们可以在处理x时,把y=target-x和x所在索引记录下来,正好分别对应Dictionary的key和value。代码如下:

  public static int[] TwoSumDictionary(int[] nums, int target)
  {
      var dic = new Dictionary<int, int>();
      for (var i = 0; i < nums.Length; i++)
      {
          if (dic.TryGetValue(nums[i], out var value))
          {
              return [value, i];
          }
          dic.TryAdd(target - nums[i], i);
      }
      return [];
  }

执行结果如下

 

运行正确,我们再来用基准测试对比一下。

 

结果和我们预想竟然不一样,还没有LastIndexOf方法效果好,哪里出了问题呢?

下面我们对这两种方法单独做一次全方面的基准测试对比,对每个方法分别用数组长度为100,1000,10000三种情况,各进行10000次测试。结果如下:

 

可以发现,只有当数组长度越来越大的时候,哈希表方案优势才慢慢体现出来。

我们再来分析一下这个算法复杂度,首先外层循环时间复杂度为O(N) ,字典操作时间复杂度为O(1),因此整体时间复杂度为O(N) 。因为字典需要额外的存储空间并且最大长度为数组长度减1,因此空间就复杂度为O(N) 。这是经典的以空间换时间方案。

从上面的对比不难发现,即使再好的方案也有其使用场景,数据量的大小,空间的大小都会制约着算法方案的选择,因此需要我们因时制宜选出最合适的方案。

没有最好只有最合适。

:测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。https://gitee.com/hugogoos/Planner

标签:target,nums,int,复杂度,题集,循环,var,LeetCode,两数
From: https://www.cnblogs.com/hugogoos/p/18389483

相关文章

  • LeetCode 热题 100 回顾
    目录一、哈希部分1.两数之和 (简单)2.字母异位词分组 (中等)3.最长连续序列 (中等)二、双指针部分4.移动零 (简单)5.盛最多水的容器 (中等)6. 三数之和 (中等)7.接雨水 (困难)三、滑动窗口8.无重复字符的最长子串 (中等)9.找到字符串中所有字母异位词 (中等)四、子串10.......
  • 738. 单调递增的数字(leetcode)
    https://leetcode.cn/problems/monotone-increasing-digits/description/classSolution{publicintmonotoneIncreasingDigits(intn){//返回单调递增的最大数字//思路比较巧妙的贪心题,需要仔细考虑两个相邻位之间的比较//一旦发现有前一......
  • Leetcode 第 408 场周赛题解
    Leetcode第408场周赛题解Leetcode第408场周赛题解题目1:3232.判断是否可以赢得数字游戏思路代码复杂度分析题目2:3233.统计不是特殊数字的数字数量思路代码复杂度分析题目3:3234.统计1显著的字符串的数量思路代码复杂度分析题目4:3235.判断矩形的两个角落是否......
  • Java LeetCode 练习
        3142.判断矩阵是否满足条件需求:        给你一个大小为mxn的二维矩阵grid。你需要判断每一个格子grid[i][j]是否满足:        如果它下面的格子存在,那么它需要等于它下面的格子,也就是grid[i][j]==grid[i+1][j]。        ......
  • 56. 合并区间(leetcode)
    https://leetcode.cn/problems/merge-intervals/description/经典题合并区间classSolution{publicint[][]merge(int[][]intervals){Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));//区间合并经典题//思路是先加入第一个......
  • 763. 划分字母区间(leetcode)
    https://leetcode.cn/problems/partition-labels/description/听说这题是字节广告一面的题有两种做法,但是思路大致相同,主要思路是先求出所有字符的出现的最远距离,然后不断往后遍历,更新当前片段的最远距离若是第一种做法,就是放在另一个循环中,不断更新最远距离,且维护这个en......
  • leetcode_128_最长连续序列解析
    题目给定一个未排序的整数数组nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。示例1:输入:nums=[100,4,200,1,3,2]输出:4解释:最长数字连续序列是[1,2,3,4]。它的长度为4。示例2:输入......
  • 435. 无重叠区间(leetcode)
    https://leetcode.cn/problems/non-overlapping-intervals/description/贪心:思路是更新重叠的区间classSolution{publicinteraseOverlapIntervals(int[][]intervals){//区间问题,首先排序,找到发生重叠的两个区间,将右边的重叠区间移除,实际对应代码的操......
  • win10 yolov8 训练问题集锦
    1.win10cmd命令行训练 要先激活虚拟环境,命令如下:D:cdD:\\ultralytics-main\\venv\\Scriptsactivate.batcd..\\..yolotraindata=D:\\ultralytics-main\\datasets\\zmbh.yamlmodel=D:\\ultralytics-main\\yolov8mepochs=5000imgsz=640batch=2workers=......
  • 452. 用最少数量的箭引爆气球(leetcode)
    https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/思路是排序,方便计算气球重叠,难点是在重叠时更新右边界,更新为两个区间的最右重合点,因为这个点是最少一支箭就可以射掉两个气球的最右点,再去下个循环判断区间重合classSolution{......