简单易懂的leetcode 100题-开篇

前言

为什么要写这个系列呢？回到了刚毕业的时候。那时候大学只是上了一门算法课程，讲解了一些基本的算法思想，和很常见的数据结构。我对算法的理解还很浅薄。
但是到了面试的时候，最短路径，贪心，动态规划，回溯，深度优先，广度优先，拓扑排序，图论，滑动窗口...各种我听都没听过的算法和数据结构接踵而至。
大厂是去不了了，有好心的公司不考算法，最后找到了一份工作。接下来工作的几年，对算法总是很恐惧，面试的时候遇到了算法考核，祈祷不要太难。
最近几年开始正视这个问题，战胜恐惧的最好办法就是正视恐惧。我们要面对他，然后把他打倒。这个系列就是据此而来。

写什么

这个系列会从投开始刷leetcode 100题，最起码保证每天一题。我会保证都是我自己理解后写出来的代码。有多种解法的题目，我会择优介绍。
最后我会给出面试的时候最好最优能通过面试的写法。希望能够帮助到被算法题目折磨的大家。

leetcode 100 链接

下面是LeetCode 热题 100的链接。leetcode地址。
https://leetcode.cn/studyplan/top-100-liked/

先介绍下leetcode平台我的一些使用经验

整个平台如下图

leetcode上的debug模式需要会员，有些题目的输入比较难构造。好在leetcode提供了标准输出，如下图。

一键添加错误的case

我觉有用的使用方法就这些了。

leetcode-001 两数之和

这是最经典的题目了，几乎99.99的刷题都是从此开始的。这道题目即使没有专门学习过算法和数据结构，我想也能够解出来。

题目描述

给定一个整数数组 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]

提示

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 仅存在一个有效答案

进阶

能否想出一个时间复杂度小于 $O(n^2)$ 的算法？

思考

这道题目是非常经典的题目，也是面试中最常考的题目。

• 暴力解法
  最容易想到的解法就是暴力解法。
  我们可以使用两层循环，外层循环遍历数组，内层循环遍历数组，判断外层循环的元素和内层循环的元素是否等于目标值。

ps： 我们为什么最先想到暴力算法。其实生活中我们一般都是这么思考解决问题的方法的。
一堆五颜六色的袜子，怎么找到另一个。暴力做法就是一个一个比较。
但是面试这样肯定是不行的。因为对于我们的写程序，数组里面的值一般来说是不确定的，可能很大（成百上千），可能很小（只有几个）。只有几个的时候暴力和优化算法的差别不大。最简单的实现反而是写一个既能应对小数据，也能在大数据量上保持性能的算法。

• 分类。也就是先把数据整理好。思考五颜六色的袜子。如果我们在配对之前先把袜子根据颜色分好类，那么发现了一个绿色的袜子，我们就可以直接去绿色的袜子对里面去找。是不是很快。更细致的，如果所有的袜子都有一个序号，同一对的袜子序号相同。我们只需要找到一只袜子后，去排好序的袜子堆里面快速找到另一只
  除了排序更好的方式是什么。就是提前放好位置。假设一个房间，有一个柜子。我们规定绿色的袜子都放在第一层，红色的都放在第二层，蓝色的都放在第三层等等。我们手里有一个绿色的袜子，那么我们就去第一层找，第一层最多可以放10个袜子，我们很快就可以在这十个里面找到另外一只袜子。这是一个近似O(1)的操作，也就是只需要一次查询查找就能获取到有或者没有的结果。利用这种思想的数据结构就是哈希。
  回到这道题目，我们先把数据进行规整，存储到哈希表里面。有人可能会重复了怎么办？这道题目是没有重复数据的，所以不用考虑这个问题。工作中遇到重复的化，我们可以在哈希表key作为查找的目标值，value作为次数。重复了就将value+1。

总结

想要在近似O(1)的时间内找到数据，可以利用哈希数据结构。对应Java里面就是HashMap，C++里面是unordered_map。

实现

下面我们用Java实现这道题目的代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numsHash = new HashMap(); // 初始化哈希结构 key是nums里面的数字 value是数组下标
        // for(int i = 0; i < nums.length; i++){
        //     numsHash.put(nums[i], i); 这里如果提前初始化 下面需要判断当前拿到的值是不是自己。所以一次循环，边循环边插入。
        // }

        for(int i = 0; i < nums.length; i++){
            if(numsHash.containsKey(target - nums[i])){ // 判断凑成targe的值是否存在
                return new int[] {numsHash.get(target - nums[i]), i}; // 有结果把数组下标返回
            }

            numsHash.put(nums[i], i); // 当前值判断之后再将放到哈希里面
        }

        return null; // 没有返回空
    }
}

下面是c++版本的

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numsMap;

        for(size_t i = 0; i < nums.size(); ++i){
            if(numsMap.find(target - nums[i]) != numsMap.end()){
                return {numsMap[target - nums[i]], static_cast<int>(i)};
            }
            numsMap[nums[i]] = i;
        }

     
        return {};
    }
};

最后

希望最后大家都能掌握这100到题目，面试顺利。