我们平时在刷题的时候，我觉得大致可分为以下几类题

1、这道题的暴力解法很简单，几乎人人都会做，但最优解却很难。

2、如果你懂某些算法思想，这道题很简单，如果不懂，那么这道题顿时很难，例如有些需要dp来处理的。

3、这种题型没做过，没啥思路，但接触过好几道之后，便会觉得异常简单，例如不能使用加减乘除运算符来完成加法运算。

4、最后一种是属于真正的难题，思路难想 ，就算知道了思想，编码也很难，因为临界点之类的特别多，逻辑特别复杂。

而我今天要强调的就是第一类题，我这里给的建议是，我们要追求极致，并且我今天会给出2道例题，大家也可以想想这2道题的解法。如果这2道题你不懂怎么做，那么看完一篇文章会有所收获。

我在牛客网刷题的时候，发现有些题的解法，如果你是采用暴力的话，是异常简单的，但是每次遇到这种题，我都不会轻易马上写代码，而是苦思一会，看看有没有优雅的解法。不过我去看很多通过的代码，发现大部分人的解法都是很普通，几乎算是暴力法，可能那些人看到这道题的时候心想：我去，又秒杀一道题了，三分钟撸好了代码，一次就ac了这道题，心里满满的快感，马上接着下一题走起。

但是，这种做法我是不支持的，因为这道题如果你草草了事，那么你没有任何优势，因为你这种解法别人也会；而且，做完这道题，你可能没有任何收获，估计只收获了快感。也就是说，做完这道题，你并没有收获到这道题最核心的解法。

所以，我觉得，对于这种题，我们一定要追求极致，不能“得过且过”。把这道题的精华吸收进来，有些题的精华、技巧，是可以开拓你的思路的，进而影响 你对其他题的解法的。

当然，收获快感提升下解题的动力也是挺好的，而且最普通的解法对部分人来说也是收获满满的。我这里只是一个建议，如果可以，请追求极致。

下面我举几个例子，也算是顺便一起来刷几道题。

案例1：构建乘积数组

题目描述：给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]A[i+1]…A[n-1]。不能使用除法。

这道题简单吗？就算不能使用除法，也是挺简单的，每次算 B[i]，都全部遍历一下数组，两个 for 循环就搞定了，时间复杂度是 O(n^2)。

但是，我敢保证，这种做法95%的人都会做，没有任何优势。所以我们想想是否有更加优雅的解法，有人说，想不出来怎么办？

很简单，想不出来就看看别人怎么做，百度搜索 or 讨论区看答案。看别人的解法，一点也不丢人。

所以对于这道题，更好的解法应该是这样的：

1、先算出 B[i] = A[0] * …A[i-1]。

2、接着算 B[i] = A[i+1]…A[n-1] * B[i](B[i]是步骤1 算出来的值)

代码如下

public int[] multiply(int[] A) {
        int len = A.length;
        int[] B = new int[len];
        B[0] = 1;
        //分两步求解,先求 B[i] = A[0]*..A[i-1];
        for(int i = 1; i < len; i++){
                B[i] = B[i-1] * A[i-1];
        }
        //再求B[i]=A[i+1]*...A[n-1];
        int tmp = A[len-1];
        for(int i = len - 2; i >= 0; i--){
                B[i] *= tmp;
                tmp *= A[i];
        }

        return B;
}

时间复杂度是 O(n)。有人可能会问，那我怎么知道这个解法是否就为最优解了呢？我觉得这个可以自己判断，加上多看一些点赞高的人的解法，如果时间复杂度、空间复杂度都和你差不多，那么几乎就可以认为是最优解了。就算实际上不是，而大佬们也都这样解，那么也可以姑且认为是最优解了。最重要的是，比你最开始想的解法好多了就行了。

案例2：数组中重复的数字

题目描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么2和3就是重复的数字了，那么可以随意返回2或者返回3都可以了，任意选择一个即可。

解法

这道题简单吗？如果只是想 ac 过去的话，那么挺简单，例如以下两种解法

1、给数组排序下，然后从左到右遍历，看看有相邻的数有没有相等即可。时间复杂度是 O(nlogn)，空间复杂度O(1).

2、用一个哈希表来存放这些数组，把数组元素值作为 key，相同元素的个数作为 value。遍历的过程中，只要发现某个 key 的 value 超过 1，那么这个数就是重复的了，直接返回。时间复杂度是 O(n)，空间复杂度是 O(n)。

这两种解法相信都不难，也很容易想到，不过请记住，很容易想到的解法大多数时候都不是最优解。那么有更好的解法吗？答是有的，更好的解法是时间复杂度是 O(n),空间复杂度是 O(1)。方法如下：

由于数字的范围是 0-n-1，那么我们可以这样做：从左到右遍历数组arr，对于 arr[i]，我们可以把arr[i]放到数组下标为arr[i]的位置上，即arr[arr[i]] = arr[i]。例如 arr[0] = 4，那么我们就把arr[0]与arr[4]进行交换。假如数组中没有重复的数，那么遍历完成后的结果是 arr[i] = i。如果数组有重复的元素，那么当我们要把 arr[i] 与 arr[arr[i]] 进行交换的时候，会发现 arr[arr[i]] 的值已经为arr[i]了，并且arr[i] != i。

没看懂？那我做个演示吧，例如数组为 arr = {2, 3, 3, 0}。步骤如下

1、从左到右遍历，此时数组下标i = 0，即arr[i] = 2。把 arr[0] 与 arr[2] 进行交换，交换的结果为 arr = [3, 3, 2, 0}。

2、i = 0,由于 arr[0] = 3，不满足 arr[i] = i,所以我们的下标还是不能右移，还是得继续交换。即把 arr[0] 与 arr[3] 进行交换，结果为 arr[0, 3, 2, 3}。

3、i = 0,此时 arr[i] = i。故下标右移，即 令 i = 1。此时 arr[i] = arr[1] = 3。把arr[1] 和 arr[3] 进行交换，但是这时候 arr[3] = 3.即此时出现了 arr[arr[1]] = arr[3]并且 arr[i] != i 的情况，故出现了重复的元素了，直接把 3 返回，遍历结束。

如果看不懂，多看两遍就能看懂了，代码如下：

   public int duplicate(int arr[],int length) {
        int i = 0;
        while(i < length){
            if(arr[arr[i]] == arr[i]){
                if(arr[i] == i){
                    i++;
                }else{
                    return arr[i];
                }
            }else{
                int tmp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] =  tmp;
            }
        }
        return false;
    }

这种方法建议大家掌握，我有好几道是遇到这种方法来处理的，例如我之前分享的几道题：【算法精讲】分享一道很不错的算法题

总结

今天 姑且分享一些对追求极致的一些看法以及举了两道题，这两道题也是自己精挑细选的，希望大家能够有所收获，并且以后做题的时候能够严格要求自己。后面我会分享后面的几类题，每次都会分享一些不过的例题，力求至少让你看完这些例题，能够有所收获。

你可能会喜欢
1、腾讯面试：一条SQL语句执行得很慢的原因有哪些？---不看后悔系列
2、为什么你学不会递归？告别递归，谈谈我的一些经验
3、一文读懂一台计算机是如何把数据发送给另一台计算机的
4、如何只用2GB内存从20/40/80亿个整数中找到出现次数最多的数
5、字符串匹配Boyer-Moore算法：文本编辑器中的查找功能是如何实现的？