从零单排leetcode——基础篇之hash算法：最简单的原则，准备一半-技术圈

作者简介

作者：水哥【清华大学信息与通信工程硕士】

原文：https://zhuanlan.zhihu.com/p/384471991

转载者：杨夕

推荐系统百面百搭地址：

https://github.com/km1994/RES-Interview-Notes

NLP 百面百搭地址：

https://github.com/km1994/NLP-Interview-Notes

个人笔记：

https://github.com/km1994/nlp_paper_study

写在前面

计算机相关专业的同学，求职，就业总避不过刷leetcode，刷算法。在笔者学习的过程中，虽然从leetcode上学到了很多东西，但是也发现一些缺点：

很多人直接贴出代码，对于思路没有讲解
有的人简要的阐述了思路，但是并没有解释怎么想到的这种解法？
感觉每一个题目都是一个单独的trick，不刷到几百道题目根本发现不了题目与题目之间的关联。

基于以上的动机，笔者就在想，我们是不是能有一个教程，把常见的规律进行总结，就像排天梯一样，从最简单的学起，由点到面，慢慢掌握规律变成算法小王子呢？于是下定决心开始本系列《从零单排leetcode》，希望每个阶段的同学，都能在里面学到一些东西。从比较现实的角度来说，能够帮助大家找实习，找工作；从比较高大上的角度来说，也能学到一些思考问题的方法。

那么，在本系列中我们追求什么？

初学者不被劝退，找到合适的学习路线慢慢掌握算法的规律
各种知识点之间建立连接关系，让每一个解法都变成能想得出来的解法
用最好懂，最详细的解释，让人人都能学会每一道题目
尽量将算法结合实际工作，避免它仅仅称为面试的工具
不停的追问为什么，挖掘深层次的原因，究其源

在本系列中我们不追求什么？

过度压缩语句，追求代码短，把一个本来多谢两句能说明白的事情变得复杂
极度追求效率，不打败100%的submission不罢休

本系列我们会跳过基本教材上的知识，比如C++的语法，堆栈是什么东西等等。中间涉及到的知识点内容读者可以google自行学习。

好，前言先到这里，下面进入主题。我们先将每一个知识点分开，对每一个知识点的各种运用从易到难进行学习。最后再进行综合。

基础篇之hash

第一节：最简单的原则——准备一半

我们第一个要讲的算法，是hash算法。这里和一般的教材顺序不太一样，为什么要先讲hash算法呢？因为它调用起来实在是太方便了。在最开始学习的时候，一句has[a]=b;是多么的方便啊！对于初学者来说，简单的调用方式能够极大程度打消畏难心理。要是一上来就各种花式动态规划，那肯定是直接劝退了。

在进入具体问题之前，还是要啰嗦一下hash到底能做什么，它最简单的用法是在 O(1) 的时间复杂度内判断某个key在不在表里，或者获取某个key的value。由于这个能力，它最重要的作用就是用 O(N) 的空间来换取（节省）O(N) 的时间。而这个能力，直接赋能了这一讲的主题——”准备一半“。

我们从一道很简单的题目开始，这道题目也是leetcode的第一道题目

1. Two Sum（Easy）
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example: Given nums = [2, 7, 11, 15], target = 9, return [0, 1].

题目的意思是在数组nums里面是否能找到两个数字，他们的和是target，本题目中比较简单的一点是，可以假设这两个答案只有一组。

好，如果我们以最简单的方式（不从算法的角度）来思考, 题目要求找两个数字合起来是target，那么可以进行就是暴力枚举，每两个拿出来试一下，这样的话时间复杂度就是

. 现在我们往下面想，根据上面hash的用法，其实可以查找某个数字有没有，那么，在每经过一个数字的时候，查找target减去这个数字，如果这个值存在于表里那么就找到了答案。这样的话每一个数字都可以只经过一遍。时间复杂度就减到了 O(N) 了。代码如下：^[1]

vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> has;// 1
        for(int i=0;i<nums.size();i++){
            if(has[target-nums[i]]>0){
                return {has[target-nums[i]]-1,i};//2
            }
            else{
                has[nums[i]]=i+1;//3
            }
        }
        return {0,1};//4
    }

这里使用了unordered_map而不是map，实际上C++中的map并不是hash实现的而是红黑树，从名字里面也能看出来，map的存储结构key是有序的。如果想学习红黑树，可以去某宇宙公司面试，包教包会
由于题目要求返回索引，所以这里的hash存储的value为索引，但是此处int默认的value是0，为了不混淆这里的0和数组索引的0，这里给所有索引做了+1
同上原因
题目本身已经保证必定存在解了，这句话不发挥作用，只是为了编译通过。

这道题目就是hash的最简单的用法，如果觉得没有基础的时候没想到使用hash，没关系，just记住它，以后自然就会用了。

不过再仔细一想，不对呀，原来的暴力算法不用负担空间消耗，只有 O(N^2) 的时间消耗，现在的做法时间空间都是O(N) 的，那不是等于说其实没有赚吗？

哎，这就突然发现了事物的本质。现在我们再讲讲形而上的一些东西，也就是上面所说的一直挖到底，复杂度的消减，不是白来的，可能通过几种方式：1.数据里面存在冗余，2.数据本身提供额外信息，3.空间和时间的互换。这三种原则对应的最典型的例子就是动态规划，二分查找和hash表。如果有懂二分查找的同学就会想到，为什么二分查找把查找的复杂度从O(N) 变成了O(logN) 呢？还不是因为数组本来有序嘛，说白了是因为他本来就提供了一些信息在里面。所以在本系列中，我们会深入贯彻这三个原则，做法就是深入挖掘数据本身的冗余，挖掘数据本身的特殊性，在合适的时候在时间和空间上做交换。

我们用两张图作为对比来区分简单的”准备全部“和”准备一半“的模式区别：

在前一个模式中，准备A花费掉一重循环，准备B还要花费一重循环，再判断。而在后一个模式中，准备A花费一重循环后，B这部分被决定了（这一点非常重要，”准备一半“可以成功的前提是，另一半是谁必须得由前一半就能决定，比如在two sum这道题目里面，target是给定的，知道了一个数字之后，另一个要找的数字就被决定了，这个时候才可以利用这个原则），之后，判断的是B。

下面再看另一道题目，也是这个原则的体现

939. Minimum Area Rectangle （Medium）
Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.
If there isn't any rectangle, return 0.
Example 1:Input: [[1,1],[1,3],[3,1],[3,3],[2,2]] Output: 4
Example 2: Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]Output: 2

根据题目要求，用这些点能组成的最小矩形。如果按照”准备全部“这个思路来做，那么需要准备四个顶点，然后进行判断，这样的话，就需要四重循环。能不能像上面一样，准备一部分，判断另一部分呢？而且上面的原则要求准备的一半能够直接决定剩下的一半，根据这四个顶点，哪些准备好之后，剩下的都可以被决定呢？

这么一梳理其实就比较清晰了，如果准备好对角线上的两个点，那么剩下两个点就被决定了，利用hash直接检查这两个点是否存在就行了。由于我们只准备两个点，那么时间复杂度就是 O(N^2) ，刚好符合我们所说的原则——“准备一半”

代码如下：

int minAreaRect(vector<vector<int>>& points) {
        unordered_map<int,unordered_map<int,int>> p2p;
        int res=INT_MAX,n=points.size();
        for(int i=0;i<n;i++){//1
            p2p[points[i][0]][points[i][1]]=1;
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(points[i][0]==points[j][0]||points[i][1]==points[j][1]) continue;//2
                if(p2p[points[i][0]][points[j][1]]==1&&p2p[points[j][0]][points[i][1]]==1){
                    int area=abs((points[i][0]-points[j][0])*(points[i][1]-points[j][1]));
                    res=res<area?res:area;
                }
            }
        }
        if(res==INT_MAX) return 0;//3
        return res;
    }

准备的部分，先把所有的点存进hash里面，这里的实现方式是嵌套了一下unordered_map，其实对于初学者来说，可能这里也会不顺畅，不过习惯了就好了。
我们只有在两个对角线的情况下，才能决定剩下的两个点，这种情况两个点出现在同一条边上，只能跳过
往往有一些corner case要记得处理一下，比如不存在解的情况。

由two sum这道题目，基本可以延伸到很多其他的题目，有些乍一看不是那么直接有关联，实际上就是一摸一样的题目，比如下面这道：

1072. Flip Columns For Maximum Number of Equal Rows（Medium）
Given a matrix consisting of 0s and 1s, we may choose any number of columns in the matrix and flip every cell in that column. Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.
Return the maximum number of rows that have all values equal after some number of flips.
Example 1:
Input: [[0,1],[1,1]] Output: 1
Explanation: After flipping no values, 1 row has all values equal.
Example 2:
Input: [[0,1],[1,0]] Output: 2
Explanation: After flipping values in the first column, both rows have equal values.
Example 3:
Input: [[0,0,0],[0,0,1],[1,1,0]] Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

题目要求经过翻转，有的行可以全部变成1或者0，最多可以有多少这样的行，这题目第一眼看有点像要动态规划的样子，实际上有点脑筋急转弯的意思在里面。我们从结果倒推：如果两个行可以经过这样的操作变成全1，或者全0，那么他们应该长什么样子？比如10011和01100就可以（翻转第二，第三列，这两行分别编程11111和00000，符合条件），10011和自己当然也可以（还是翻转第二，三行，都变成11111），只要细心观察就会发现这里的两个行要么是完全一样，要么就是互补的！所以能形成全0或者全1的行的最大数目就是看每一行和互补的行的总数有多少就行了，这其实就和two sum这种典型的hash是一样的，这样就可以写出答案：

int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        map<string,int> has;
        for(int i=0;i<matrix.size();i++){
            string tmp;//1
            for(int j=0;j<matrix[i].size();j++){
                tmp+=to_string(matrix[i][j]);
            }
            has[tmp]++;//2
        }
        map<string, int>::iterator iter;
        int res=0;
        for(iter=has.begin();iter!=has.end();iter++){
            string rev;
            string tmp=iter->first;
            for(int i=0;i<tmp.size();i++){
                if(tmp[i]=='1') rev+="0";
                else rev+="1";
            }//3
            res=max(res,has[tmp]+has[rev]);
        }
        return res;
    }

这里我们把每一行作为一个key，但是并不是把整个行作为vector来作为key，而是转化成字符串（如果列不是很多当成二进制转int也可以），比较节省空间。
准备工作，先把所有的行存下来。
和two sum一样，每次经过一个行，计算一下它的”补行“，最终结果就是这种行的个数加上补行的个数。

以上就是本讲的例题内容，作为一个号称要活学活用的系列，这里也推荐一下相关的练习题：

No.535 了解hash算法，复现，最基本的运用。
No.136 singlenumber，一道知名度很高的题目，可以先从hash的角度练习
No.349 No.781也是hash的简单用法
No.454 几乎就是two sum的原版

最后再闲扯一些别的，大家对算法题的吐槽往往都是觉得这些题目和实际工作完全没有关系，只是一些trick的堆叠。这个感觉我也有过，不过不吹不黑，这里首先要把hash拿掉，因为它可以说是最接地气的算法了。每一个算法工程师，掉包侠总免不了要和dict打交道，机器学习一些应用场景里面也常常要用到lmdb。在日常的工作中，总不可能随便取一个sample，都要把数据集遍历一遍，可以这么说，hash从 O(N) 到 O(1) 的一大步，是你我工作中的一大大步（滑稽）

下期预告《从零单排leetcode——基础篇之hash算法：脑海触发器，哪里该用hash》

参考

^本系列中统一使用C++作为编程语言，虽然算法同学们大多数是使用python