写在前面的话

算法无用论和算法重要论一直以来都是程序员界争论不休的话题，至今也没人能给出一个明确的定论。个人认为，解算法或者说刷题的目的不在于我们在工作中使用这个算法，而在于解题的过程能锻炼我们解决问题的思维和扩展思维。这种思维可以给我带来的是：一个复杂的流程可以想到多种解决方法，并且从中选择最优的解法，而不是只有一种解法还是十分垃圾的解法。另外，一个简单的数据结构的使用可能会大大的简化我们代码的时间复杂度（时间复杂度和空间复杂度的概念请自行了解）。下面来看例子吧（以下问题中，所有整数都在32位整型范围内）：

一、缺少了谁？

问题一：有n个数 nums，1 <= nums[i] <= n，无序无重复，被拿掉了一个，请找到被拿掉的那个数，例如：

1
2
3
nums = [2,6,4,3,1]; n = 6;
result: 5.
// 6个数：1-6，被拿掉的那个是5，所以结果就是5。

解法：用等差数列求和公式得到 n 个数的和，然后把数组中的数字挨个减一遍。直接上代码：

1
2
3
4
5
6
7
8
9
int findAbsence(int[] nums, int n) {
    if (nums == null || nums.length == 0) return -1;

    int sum = (1 + n) * n / 2;
    for (int i: nums) {
        sum -= i;
    }
    return sum;
}

看上去也没有什么难度嘛！而且此解法的时间复杂度为 O(N)，空间复杂度为 O(1)，简直完美。

上面的解法已经是这道题的最优解法，但是它不具备通用性，假如我们遇到的问题不是抽掉一个数字而是两个呢？那么上面的解法就不具备解决这个的问题的能力。

问题二：在问题一的基础上，扩展为拿掉两个数字或者更多数字，例如：

1
2
3
nums = [2,6,4,1]; n = 6;
result: [3,5].
// 6个数：1-6，被拿掉的那个是5，所以结果就是5。

很显然，问题一的解法显然已经不适用于现在的问题了，有的人可能会想到先排序，然后比较数组的下标和对应的值，当第一次出现不对应的时候就是缺少的值，同样的方法再找到第二个，但是排序的时间复杂度是 O(N*lgN)，该题目可能还会有更好的解法。

散列法（什么是散列表），将数组中的值全部散列到 Map 中，然后将 1 - n 作为键去 Map 中查找，查不到的即为缺少的。代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
List<Integer> findAbsenceWithMap(int[] nums, int n) {
    if (nums == null || nums.length == 0) return null;
        
    List<Integer> list = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
        
    for (int i: nums) {
        map.put(i, 1);
    }
        
    for (int i = 1; i <= n; ++i) {
    	if (map.get(i) == null) {
            list.add(i);
        }
    }
    return list;
}

我们用了 O(N) 的空间复杂度换取了 O(lgN) 的时间复杂度，同时这种解法好像更容易理解一些。

这种解法 O(N) 的时间复杂度当然是建立在哈希表没有哈希冲突的情况下，假设在极端情况下哈希表完全冲突，那么该问题的时间复杂度变成了 O(N^2)，好像还不如我们第一次想到的排序算法，当然哈希完全冲突的情况基本上不会出现，作这个假设的目的是为了引出更好的解法：

申请一个新的数组，数组的长度为 n，将 nums 中的值作为下标，将 nums 中的内容散列到新的数组，标记为 1，最后遍历一遍新数组，未被散列的下标即为我们要查找的目标：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
List<Integer> findAbsenceWithArray(int[] nums, int n) {
    if (nums == null || nums.length == 0) return null;

    List<Integer> list = new ArrayList<>();
    int[] temp = new int[n];
	
    // 注意：数组的下标从 0 开始
    for (int i: nums) {
        temp[i - 1] = 1;
    }

    for (int i = 0; i < n; ++i) {
        if (temp[i] == 0) {
            list.add(i + 1);
        }
    }
    return list;
}

这样就解决了哈希表哈希冲突的问题，同时基础类型的数组要比 Map 这种封装类型对内存的消耗少得多。

二、多了谁？

现在问题又变得复杂了：

问题三：依然是 n 个数，每个数的大小都大于等于1，小于等于 n，但是有的数被拿掉了，有的数出现了两次，请找到出现两次的数。例如：

1
2
3
nums = [2,6,6,4,2,1]; n = 6;
result: [2,6].
// 2和6分别出现了两次，缺少了3和5。

经过对问题一和问题二的思考，我们马上就想到了，将所有数以数为键，以出现的次数为值散列一遍，最后找到哈希表中值为 2 的数，emm，是个好解法，但是不幸的是，此时待处理的数组过大，已经没有多余的内存给你申请一个相同内存的数组或者哈希表，也就是说我们必须要在 O(1) 的空间复杂度解决这个问题。同时，由于待处理数组太大，我们设计的算法的时间复杂度不宜过高。

现在看上去这个问题是有点变态了，但是又确确实实是我们在工作中可能会遇到的问题，因为 4G 内存装满整形数字也就 10亿数量级的数字，好像并不是特别大。

好在，题目并没有不允许我们修改原始数组，题干中的 1 - n，好像也是解题的关键所在。因此，我们就想到了原地散列的解法，也就是以数组中的值为下标再散列该数组，将该下标下的值乘以 -1，当遍历到某个下标的值小于 0时，则该下标出现两次。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 原数组
key: 0 1 2 3 4 5
val: 2 6 6 4 2 1
// 将第一个 val，数组中的第二个数乘以-1
key: 0  1 2 3 4 5
val: 2 -6 6 4 2 1   
// 将第二个 val，数组中的第六个数乘以-1
key: 0  1 2 3 4  5
val: 2 -6 6 4 2 -1 
/* 遍历到第三个val，6时，发现数组中第6个数为负数，说明6是第二次出现，
 * 因此，6为出现两次的数，保存6。
 * 然后将第6个数乘以-1，避免重复，以此类推。
 */
key: 0  1 2 3 4  5
val: 2 -6 6 4 2  1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> findDuplicates(int[] nums) {
    List<Integer> list = new ArrayList<>();

    if (nums == null) return null;
    if (nums.length == 0) return list;

    for (int i = 0; i < nums.length; ++ i) {
        int index = Math.abs(nums[i]) - 1;
        if (nums[index] < 0) list.add(Math.abs(index + 1));

        nums[index] = -nums[index];
    }

    return list;
}

这样我们就用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决了这个问题。

经过上面几道题目的锻炼，感觉自己好像掌握了解决这种问题的套路了，自信满满。放马过来吧！🤓🤓

问题四：这次不再是 n 个数了，而是 n + 1 个数，仍然是大于等于1，小于等于 n，但是这堆数里面出现了一个异类，它出现了两次，并且只有它出现了两次，例如：

1
2
nums = [2,5,1,1,4,3]; n = 5;
result: 1.

条件继承自问题三，没有多余的空间给我们用，时间复杂度不宜过高，但是不同的是，此时你不能再修改数组了。

假如没有这些条件的话，上面几个问题的解法看起来好像都能解决这个问题，我们的铺垫是有用的，但是假如加了这些限制条件，你还能想到解法吗？要知道永远不会变的是变化，你怎么保证自己的职业生涯中不会遇到这类问题和限制条件呢？

那么现在就开始解决它吧！

数组中的值分布在 1 ~ n 之间，除了散列，还能想到什么数据结构能满足这个条件呢？答案是链表。用数组实现的链表，听起来好像有点陌生，那就去翻翻那本叫数据结构与算法的大学课本吧！

通常数组都是以下标 0 开始的，那么我们先将 1 ~ n 转化为 0 ~ n：

1
2
3
4
5
6
// 原数组
key: 0 1 2 3 4 5
val: 2 5 1 1 4 3
// 转化后
key: 0 1 2 3 4 5
val: 1 4 0 0 3 2

现在看上去好多了，数组中存的值可以和下标对应了，我们将转化后的数组写成链表：

是不是看上去大吃一惊，还能这样玩？别着急，好戏还在后面呢。

现在的目的有点明确了，我们要找的就是这个有环的链表的环开始的地方，就是那个结点 0，当然它在原数组中的大小是 1，将链表中的每个结点转化为原数组中的值只需要将他们的大小加 1 而已，就像我们将数组转换为链表的时候减 1 一样。

如何找到这个环开始的结点？即，如何找到链表的环开始的结点？

emm，挨个将每个结点放入 Set，当第一次遇到存放失败，即 Set 中存在该结点的时候，这个结点就是要找的结点。是个好主意，但是，是不是忽略了最初的限制条件？即使现在变成链表的结构了，我们也没有多余的内存去申请一个 Set。

事情好像又陷入了一个死结。

那么两个指针呢？一个一次走一步，一个一次走两步，当走的快的指针追上走的慢的指针的时候，是不是就说明链表有环？

首先我们假设链表有环，并且两个指针能相遇，并且在慢指针走了 k 步后相遇，此时快指针走了 2k 步，那么快指针比慢指针走的多的步数就是环的长度乘以循环的次数。假设环的长度为 r，快指针循环 n 次相遇，那么我们可以得到结果：2k - k = nr，因此当 n 满足 k = nr 时，两个指针相遇，证明了我们的假设。看来这个办法是行得通的，但是，我们没有办法保证此时相遇的结点即为环开始的结点，只能证明它们会在某处相遇而已，即只能证明链表有环。

那么环开始的结点在哪呢？

在上面的基础上继续推导，如上图，设链表的头结点为第 0 步，环的方向为逆时针方向，环开始的结点到头结点的距离为 m 步，快慢指针相遇的结点到头结点的距离为 k 步，m 到 k 的距离为 s 步，所以，我们可得到：s = k - m，即，s = nr - m，即 s = (n - 1)r + r - m，当 n = 1时，s = r - m，即 m = r - s。也就是逆时针方向 k 到 m 的距离等于头结点到环开始的结点的距离，因此，我们让快指针重新回到头结点，慢指针仍然在相遇结点，两个指针都一次走一步，它们相遇的结点即为我们要找的结点。

Talk is cheap, show you the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findDuplicate(int[] nums) {
    if (nums == null || nums.length == 0) return -1;
    /* 不用刻意的去寻找头结点
     * 即使上述推论中 m = 0，也能得到相同的结果。
     */
    int slow = nums.length, fast = nums.length;

    // 因为都是从头结点开始的，所以忽略第一步判断
    do {
        slow = nums[slow - 1];
        fast = nums[nums[fast - 1] - 1];
    } while (slow != fast);

    slow = nums.length;
    while (slow != fast) {
        slow = nums[slow - 1];
        fast = nums[fast - 1];
    }

    return slow;
}

想不到吧，一个复杂的问题居然可以用这么少的代码就解决了，所以，算法的优势显而易见，如果此时你还坚持算法无用论的话，那么下面这个问题呢？

三、谁是单身狗？

问题五：现在情况又有些不同了，你遇到的问题不再是 1 ~ n 之间的数字了，变成了任意整数，但是这些数中只有一个小伙伴只出现了一次，其他小伙伴都出现了两次，同样你没有多余的内存可用，也就是别想 Map Set 等数据结构会来帮你，如果认为排序是个好办法的话，不好意思，我们最好将算法的时间复杂度控制在线性时间复杂度之内，因为这个数据量可能会超出你所能想象的大小，并且除了某些特殊情况下，修改原数组不是一个很好的解题习惯。

考验基础牢固不牢固的时候到了，当我们把一个数字转换成二进制的时候，就可以对它进行位操作，比如按位或、按位与、按位异或、左移、右移等等。比如：

1
2
3
4
5
3: 0 1 1
5: 1 0 1
&  0 0 1 // 与
|  1 1 1 // 或
^  1 1 0 // 异或

那么当两个数相等时，他们的位操作的结果呢？

1
2
3
4
5
3: 0 1 1
3: 0 1 1
&  0 1 1 // 与
|  0 1 1 // 或
^  0 0 0 // 异或

问题好像有点眉目了，两个相等的数异或的结果就是 0，我们想一下就能知道，0 与任何数异或的结果都是任何数，因此，3 ^ 3 ^ 5 = 5。有了这个结果，那么写代码吧（假定数组非空）：

1
2
3
4
5
6
7
8
public int findSingle(int[] nums) {

    int res = 0;
    for (int i: nums) {
        res ^= i;
    }
    return res;
}

请问你现在还抱着算法无用论的心理吗？？

写在最后的话

多余的话就不用再说了，算法的存在不在于解题，而在于锻炼这种解题的思维。

另外，如果你也对算法有兴趣的话，来体验解题的快感吧： LeetCode，这里 有我解的一部分问题的 Java 实现，有些可能不是最优解，按题目类型分类，用题目的 title 搜索也能找到哦。