刷个算法，结果第一题就蚌埠住了~~

作者：为自己带盐

2022 年 7 月 05 日
本文字数：1312 字
阅读完需：约 4 分钟

前言

本来计划今天分享一个第三方的控制台工具的，可以做出漂亮的控制台项目。但今天还是因为加班有点晚了，到我打开 infoq 的时候，都已经晚上 9 点多了。

想要快点搞完，还不想耽误休息，琢磨了一会儿。。。要不刷个算法吧（此时特别想手动艾特某人...还是某水货）。

想起年初里的 flag，有个刷够多少个算法题，正好就从今天开始吧。

最热的 100 道算法题之第 1 题(即最简单的一道题)

哈哈，标题有点长~~

因为这道题上来就给我干蒙了啊，琢磨了一会儿，写出了最直观的解法。

来看下第一题的内容，传送门：两数之和

给定一个整数数组 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]
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/two-sum

复制代码

最简单的题之最简单的解法

这个题看起来挺简单吧，我第一次花了大约 10 分钟左右琢磨，然后本来想直接在输入框里写答案的，后来还是开了个编辑器自己跑了一下，这一跑，又花了大约 10 分钟~~当然用的也是最野蛮粗暴的解法。

如下

 public static int[] TwoSum(int[] nums,int target) {   for (int i = 0; i < nums.Length; i++)   {     for (int j = i + 1; j < nums.Length; j++)     {       if (target == nums[j] + nums[i])       {         Console.WriteLine($"[{i},{j}]");         return new int[] { i, j };       }     }   }   return null; }

复制代码

本地跑了几个用例，发现没啥问题，就到页面提交去了，结果也算是答对了吧，然后我看绝大部分同学都能写出这个最简单的写法。

对了，第一次解答错误，是因为我从本地复制到答题窗口的时候少复制了一个大括号，导致的。

到这就结束了？

当然不行！为啥，看看这运行结果

自尊心比较强的我当然不能接受！

然后，我也的确一时半会儿没有想到性能更好的解题方法来，😅

怎么办呢，我就看了一下官方的题解思路。

他是这么写滴

其实，我也想到用哈希表来做了，但一时半会儿没有想出来具体的方法（一定是因为太晚了，我太累了！！）

哎，看到他这思路，（当然了，下面的 java 代码也就没忍住看了一眼）

真是秒啊，具体的接替方法我就不赘述了，就是利用哈希减少遍历的次数，提高效率。总的来说就稍微转了一个弯，设计哈希结构的时候，把目标值当成键值存到哈希表的 key 里，把索引值存到 value，一切就解决了

来看下改造后的 C#代码

Dictionary<int, int> dic = new Dictionary<int, int>();for(int i = 0; i < nums.Length; i++){  if(dic.ContainsKey(target - nums[i]))  {    return new int[] { dic[target - nums[i]], i };  }  dic[nums[i]] = i;}
return null;

复制代码

这次在提交，看下运行结果