你有被三数之和难倒吗-一一网

前言

前段时间我的一个朋友去面了airwallex，最后做了一道算法题，是个三数之和的变种问题，并且被要求把时间复杂度优化到O(n^2)。恰巧这个问题我之前面顺丰时也做过嘞~?

题目大概是这样的：给定一个整数数组arr跟一个整数n，判断数组里是否存在三个整数加起来和等于整数n，存在的话返回true，不存在的话返回false。

这道题本身不难，我们可以稍微拿出来说一说。而且不用我们找到所有三个数之和等于给定整数n的情况，岂不是美滋滋？

方案一：直接暴力解决

拿到手我第一反应基本上都是先通过暴力循环解决这个问题，后面再慢慢优化。我们要找的三个数a、b、c得是数组不同索引上的元素，第一层循环我们找到a，然后第二层循环我们在a之后的元素中去寻找b，(为什么在a后面找b，因为前面的情况a已经试过了，c同理)最后再一层循环去找c，直接嵌套三个循环判断三个数之和能不能满足条件。这个逻辑比较简单，我们来直接看代码：

 public static boolean findSumOfThree(int[] arr, int requiredSum) {
        for (int i = 0; i < arr.length - 2; i++) {
            for (int j = i + 1; j < arr.length - 1; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    int sum = arr[i] + arr[j] + arr[k];
                    if (sum == requiredSum) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {3, 7, 1, 2, 8, 4, 5};
        int[] requiredNums = {10, 20, 21};

        System.out.println("1. Original array: " + Arrays.toString(arr));
        for (int test : requiredNums) {
            if (findSumOfThree(arr, test)) {
                System.out.println("   Sum for " + test + " exists ");
            } else {
                System.out.println("   Sum for " + test + " does not exist ");
            }
        }
        System.out.println(
                "------------------------------------------------------------------------------------------------------\n");

        int[] arr1 = {-1, 2, 1, -4, 5, -3};
        int[] requiredNums1 = {-8, 0, 7};

        System.out.println("2. Original array: " + Arrays.toString(arr1));
        for (int test : requiredNums1) {
            if (findSumOfThree(arr1, test)) {
                System.out.println("   Sum for " + test + " exists ");
            } else {
                System.out.println("   Sum for " + test + " does not exist ");
            }
        }
        System.out.println(
                "------------------------------------------------------------------------------------------------------\n");
    }
复制代码

这边我们也写了test case来测试一下啊，除了复杂度高没啥问题哈~（这边时间复杂度O(n^3),空间复杂度O(1))

那我们有什么办法可以避免三次循环带来的开销呢？如果我们拿到了一个数a，那我们其实要找的是有没有两个数之和加起来等于n-a，这个逻辑没问题吧，然后这个问题就分解成找到两个这样的数。这不就联系到我之前讨论过的双指针的问题上来了吗？！！关于双指针，不了解的朋友可以看这里：双指针。

方案二：双指针

这里我们并不知道哪个数是符合条件的三个数之一，所以对于这第一个数a，我们得循环一次遍历整个数组，首先假设它是，然后找存不存在其它两个数。

而且需要注意的是，双指针只适用于输入的数组是有序的情况，这里我们要对输入数组进行排序。

public static boolean findSumOfThree(int nums[], int requiredSum) {
        // 输入数组不一定是有序的，先对数组排序
        Arrays.sort(nums);

        // 双指针中从前往后的指针
        int low;
        // 双指针中从后往前的指针
        int high;
        // 记录当前三个数的和
        int triples;

        // 对于第一个数，遍历整个数组
        for (int i = 0; i < nums.length - 2; i++) {
            // 把低位指针设置成剩下的数中的第一个
            low = i + 1;

            // 从末尾开始
            high = nums.length - 1;

            while (low < high) {
                // 判断是否满足条件
                triples = nums[i] + nums[low] + nums[high];
                if (triples == requiredSum) {
                    return true;
                }
                // 如果小于requiredSum，把低位指针往后移，以让triples更大些
                else if (triples < requiredSum) {
                    low++;
                }
                // 把高位指针往前移，以让triples更小些
                else {
                    high--;
                }
            }
        }
        // 找不到啦
        return false;
    }
复制代码

这里测试用例不变，我就不再贴出来啦，由于减少了循环的次数，这边我们的时间复杂度降到了O(n^2)，空间复杂度也变成了O(1)。

有的时候面试官并不想让我们改变原数组，那如果输入数组不是有序的，我们排序这一套操作就不好使了。

方案三：缓存用上，空间换时间

本质上，对于第一个数a，我们拿到另一个数b时，我们想尽可能快地判断数组里有没有另一个数c能够满足条件，所以我们一开始才又做了一次循环。

但是循环太耗时了，还有什么办法能比循环还快呢？这得提一提查找元素时间复杂度可以达到O(1)的哈希表。哈希表嘛，大家都很熟悉，牺牲空间以获得超快的查找速度的数据结构。要是我们把数组里的元素都记录在哈希表里，那我们不就可以在已知a、b的情况下判断有没有符合条件的c了么？！

我们不能直接遍历一遍数组把所有元素添加到哈希表中，因为a、b、c得是不同索引上的元素。如果在确定a、b之后再循环一次把其它元素添加到哈希表中，那我们的时间复杂度还是O(n^3)，用哈希表就没有意义了。那怎么办？无解了？？

其实第二次循环找b的时候，我们不就确定a、b了吗，我们只要把a之后，b之前的元素添加到哈希表里就好了。可能有同学会担心b之后的元素此时还未遍历，没关系，随着b逐渐靠近数组末尾，我们的c的可选值也会逐渐覆盖数组里所有的值。

这里由于我们最后要记录的仅仅是一个元素，我们可以换成HashSet来完成我们的算法：

public static boolean findSumOfThree(int[] nums, int requiredSum) {
        // 这边我们用HashSet就可以了
        HashSet<Integer> hashset = new HashSet<Integer>();

        // 对于第一个数，我们还是要遍历整个数组
        for (int i = 0; i < nums.length - 1; i++) {

            // 清空上一轮循环放入的值
            hashset.clear();

            // 用于记录另外两个数的和
            int sumOfOther2Num = requiredSum - nums[i];

            for (int j = i + 1; j < nums.length; j++) {
                // 计算需要的最后一个数
                int numNeeded = sumOfOther2Num - nums[j];

                // 判断这个数之前有木有遇到
                if (hashset.contains(numNeeded)) {
                    return true;
                }

                // 没遇到，把这第二个数添加到HashSet
                hashset.add(nums[j]);
            }
        }
        return false;
    }
复制代码

齐活儿了！这样我们的时间复杂度还是O(n^2)，只不过空间复杂度变成了O(n)。