今天和前同时闲扯了几句，聊到他最近去面试谷歌，几面下来还没问到项目经验，全都是算法题，感慨算法没有好好积累。
今天，我们来谈一谈一种问题的解决思路，降维！
题目：
在 一个X * Y的地图上，要建立3个巡逻点，每个点的坐标都是整数，并且3个点的x坐标，y坐标都不相同， 1 <= x[i] <= X, 1 <= y[i] <= Y。在这个图中点i跟点j的距离定义为abs(x[i] - x[j]) + abs(y[i] - y[j])。现在我们希望三个点两两的距离之和大于minT，并且小于maxT。求方案数。
1 < X, Y < 4000
思考：
这个题目可能有点复杂，我们先通过一个简单的例子来说明下这个问题。假如X = 3, Y = 3，那么满足条件的x坐标都不同,y坐标都不同的总共有6种情况，分别是：
(1,1)(2,2)(3,3)
(1,2)(2,3)(3,1)
(1,3)(2,1)(3,2)
(1,1)(2,3)(3,2)
(1,3)(2,2)(3,1)
(1,2)(2,1)(3,3)
通过计算，我们发现他们的距离之和都是8
好了，但是我们仍然不知道这个问题要如何求解！
干货1：
降维。我们看一看这个距离的计算公式abs(x[i] - x[j]) + abs(y[i] - y[j])，我们发现x轴跟y轴没有必然的联系，那么我们可以考虑将x轴跟y轴分开！最后的总距离为x轴的距离加上y轴的距离。
我们再来看一看x轴的距离怎么算，假设x1 < x2 < x3,那么
totalX = (x2 - x1) + (x3 - x1) + (x3 - x2)
= 2(x3 - x1)
我们惊讶的发现，这个距离竟然只跟x1,x3有关系，并且是他们的差的2倍。同理y轴也只跟y1,y3有关。如果看不懂公式的，我们可以简单地画个图。
走的路程其实就是一个矩形，只跟最大最小有关（画的不太标准。。见谅）。
当我们确定x1,x3的时候，x2的选择是(x3 - x1 - 1)种。
我们定义fx[k]表示，x轴上的距离为k时，总共有多少种不同的情况，我们枚举x1,x3的大小，可以轻易算出fx的结果。
同理我们处理fy[k]。
把这两部分都处理完后，我们通过枚举在x轴上面的距离，还有在y轴上的距离，计算出最后的结果。
当然这还不够，我们的结果还要乘以6。因为当x轴确定的时候，y轴的三个y可以来一个排列。我们来看一看代码。（代码最后取了一个模）。
这部分是用来计算fx的代码。
这个是用来计算最后的结果。我们对最后结果取一个mod 因为比较大。
总结：
降维，是我们常用的解决问题的一种思路，通过固定一维，或者进行纬度分离，我们经常能找到问题的突破口。
最后欢迎大家关注我的头条号，定期推送面试相关还有码农码禽码畜感兴趣的东西。当然，如果大家有什么看不懂的，可以提出来，沙茶敏都会耐心为大家解答。。。或者想沙茶敏整理哪一方面的面试题目，可以在评论中说出来。
