N-Sum 问题

最近在准备面试,所以一直在刷算法题。然后越准备越发现不论是哪个公司,面试问的算法问题基本上都很水。我这里说的“很水”并不是所有的题我都能做出来,有些问题没见过类似的还是不太好想的。而是这些问题基本上都围绕着二分查找、链表、递归之类的在转圈圈。例如下面一些“水题”:

  1. 有一个有序数组,但是数组有可能被“右移”或者“左移”过,比如 [3, 5, 6, 7, 1, 2] 之类,要你写算法查找某个元素或者给出插入的下标。
  2. 有一个有序数组,除了某个元素外每个元素都恰好有 2 个,要你找出这个元素(要求 log n)。
  3. 有一个有序数组,里面元素有些有重复,给定一个元素,要你查找这个元素在这个数组里的范围(要求 log n,所以不要想着找到后前后遍历)。
  4. 有一个有序数组,里面大量元素是重复的,要你写一个算法,求出这个数组里一共有多少个不同的元素(要求 log n)。

诸如此类的“二分查找”的变种我随便就能说出一大堆。我实在是不明白老问这些问题有啥意义,考察你手写代码时的细心程度么?考察你代码写得规不规范么?众所周知,贪心、分治、回溯、分支限界以及动态规划是算法界的五大法宝,可是这些都在面试时很少涉及,尤其是动态规划。乃别告诉我写个二叉树遍历或者八皇后就叫做考察了回溯,连个剪枝都没有,乃确定这样的面试能够筛选出合适的人?

吐槽归吐槽,还是要按照实际情况来的。比如我一直想不通高考的古诗词默写有个毛意义,考察记忆力么?如果不是特别对古诗词感兴趣的,高考完后基本都会全忘掉(比如乃现在还能记得“路漫漫其修远兮,吾将上下而求索”的前一句么?),那和没有背有啥区别?不过乃也不能因为没有而不准备不是?

言归正传,这里老夫要记录一下 k-Sum 问题的解法。

这类问题是这样的,有一个数组里面有一堆元素(没排序),要你找出 k 个元素,使它们的和恰好等于 s。

 

1-“Sum”

特么一个元素还叫 Sum?老夫只是为了引出这个问题,也就是说我们要在这个数组里找出某个元素 s。

很显然只能暴力地去遍历整个数组,时间复杂度为 O(n)。如果先排序后二分,那么针对只需要搜索一次的情况就是 O(nlog n)了,得不偿失。

 

2-Sum

至于找出 2 个元素使它们的和等于 s,其实有个 O(n) 的算法。其实比较容易想到的是排序后用首位两个指针不断地移动,在查找过程中复杂度就是 O(n) 了,不过排序还需要 O(nlog n)的复杂度。

既然要 O(n),那么只能空间换时间了(实际上 O(nlog n) 的排序也需要辅助空间)。知道可以用辅助空间后,那问题就很简单了,遍历到某个元素 a[i] 后只需要知道数组里有没有 s – a[i] 就可以了,显然用哈希表就能解决。

(用了这个 bug 一大堆的插件后,泛型的类型都丢了,而且有些显示不正常,凑合着看吧。)

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> hash = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (hash.containsKey(target - nums[i])) {
            return new int[] { hash.get(target - nums[i]), i };
        }
        hash.put(nums[i], i);
    }

    return null;
}

要说对付这种很水的面试,哈希表是一个大神器。比如老夫以前面试时就遇到过这个问题的变种:

给你一个整型数组,任意取其中连续一段,比如 a[m .. n],把这些元素进行“按位或”操作 a[m] | a[m + 1] | … | a[n],其结果记为 k。问乃在这个数组中, k 一共有多少种不同的取值。

 

3-Sum

现在考虑三个元素情况。如果采用暴力搜索,那复杂度就是 O(n^3),所以我们要找的方法就是低于这个复杂度的算法。回想一下我刚才在两个元素时提到的那个排序后用 O(n) 找出两个元素和为某一数值的算法,这里正好可以派上用场。

先把数组排序,枚举第一个元素 a[k],那么接下来我们就要在 a[k + 1] .. a[n] 中找出和恰好为 s – a[k] 的元素了(乃说为啥不考虑 a[0].. a[k – 1] 之间的元素?特么枚举到 k 之前已经包括了啊)。接下来我们用两个指针 l 和 h 分别指向 k + 1 和 n 这两个位置,如果这两个指针指向的元素相加正好等于 s – a[k],那么很好我们就找到了一种情况(不过别急着把循环 break 掉,因为还有可能有其他解)。如果大于 s – a[k] ,就把 h 往前移一个位置,由于数组是单调递增的,把 h 往前移后结果必然会减少或者不变。如果小于,则 l 往后移。

由于 l 和 h 最终会交汇,因此我们只需要枚举 n – k 次,另外我们还需要枚举第一个元素 n – 2 次,因此总的复杂度是 O(n^2)。

看似问题解决了,可是如果题目要求你找出不同的结果集呢(相同数组不同下标视为相同的结果)?此时我们就要把重复的结果过滤掉。在返回结果之前用暴力搜索过滤掉重复结果自然是可以(因为毕竟我们的复杂度已经是 O(n^2) 了),但实际上我们在枚举的过程中就能把重复的结果去掉。

在枚举第一个元素的时候,如果遇到与上一个相同的元素我们可以直接跳过。同样在 l 和 h 移动的过程中我们也需要跳过与上次相同的元素。但是要特别注意只有在找到结果后才跳过一样的元素,一定不能在没找到结果时就跳过重复的元素。比如如果我们有 [1, 1, 1, 3, 4],我们要查找 2,如果一开始就跳过相同元素使 l 移动到了 3 的位置,那 1, 1 就找不到了。

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();
        int l, h;

        for (int i = 0; i + 2 &lt nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;  

            int rest = -nums[i];
            l = i + 1; h = nums.length - 1;
            while (l < h) {
                if (rest == nums[l] + nums[h]) {
                    result.add(Arrays.asList(nums[i], nums[l], nums[h]));
                    while (l < h && nums[l] == nums[l + 1]) l++;
                    while (l < h && nums[h] == nums[h - 1]) h--;
                    l++;h--;
                } else if (nums[l] + nums[h] > rest) {
                    h--;
                } else {
                    l++;
                }
            }
        }

        return result;
    }

 

问题变种:雨水问题

(问题来源:LeetCode 第 42 题)有一个凹凸不平的池子,每一块宽都为 1。池子两侧没有盖子而前后有盖子,如下图所示。现在下雨了,问这个池子能装多少水。

输入:一个数组 a[0..n],a[i] 表示 坐标为 i 的区域高度为 a[i]。

输出:能装的水的面积(在这里看成是二维的)。

乃不妨自己先想想再看下面的解答。

————————————————————————————————————————

————————————————THINKING...—————————————

————————————————————————————————————————

其实这个问题和 k-Sum 关系不大,但是也可以用两个指针互相靠近就能搞定,有点类似上面的解法,所以我把它当成是“变种”问题。乃貌似不太服?怎 yan(和某个发音不标准的同事学的),乃打我呀!

以上面那张图为例,假如我们的指针 l 和 h 在 3 、7 这两个位置,也就是下面红框内的区域:

此时,雨水一定不能比左边的位置高,但是低于左边高度的区域一定能装雨水!也就是说,我们可以右边不动,移动左边的指针来统计雨水的面积,对于某个高度是 a[i] 的区域,它能装的雨水就是  a[l] – a[i]。那如果遇到了一个比 a[l] 高的位置怎么办呢?很简单,此时判断 a[i] 和 a[h] 哪个比较高,移动矮的那个就可以了!

至于由于池子左右没有板子,所以要过滤掉不能装水的地方,直到碰到递减的高度之前,都是装不了水的。

    public int trap(int[] height) {
        int v = 0;
        if (height.length < 3) return 0;

        int l = 0, r = height.length - 1;
        while (l < height.length - 1 && height[l] < height[l + 1]) l++; 
        while (r > 0 && l < r && height[r] < height[r - 1]) r--; 
        if (l >= r) return 0;

        while (l < r) {
            int hl = height[l], hr = height[r];
            if (height[l] <= height[r]) {
                while (l < r && hl >= height[++l]) {
                    v += hl - height[l];
                }
            } else {
                while (l < r && hr >= height[--r]) {
                    v+= hr - height[r];
                }
            }
        }

        return v;
    }

 

4-Sum

回到主题上,现在要找出 4 个元素和为 s,咋找?如果模仿 3-Sum 的做法,那我们就需要枚举前两个元素,复杂度是 O(n^3),有没有更好的方法呢?

还记得我们做 2-Sum 吗?我们用了一个哈希表来判断有没有 s – a[i] 的元素。那我们就可以想到:如果把这 4 个元素两个两个一组,不就能用类似的办法了吗?所以我们可以想出如下算法:

  • 枚举数组 a 中任意两个元素相加的所有可能性放到一个排好序的数组 S 中。由于一共有 n 个元素,枚举需要 O(n^2) 的复杂度,之后对这 n^2 的元素排序(注意!两两相加最多有 n^2 种结果),所以复杂度是 T(n^2*log (n^2)) = T(n^2*2*log n) = O(n^2*logn)。
  • 接下来就容易了,遍历 S 中的每个元素,看看 S 中有没有 s – S[i] 就好了,如果有,组合一下就是结果。由于 S 是有序的,因此遍历时复杂度是 O(nlogn)。

因此总的复杂度是 O(n^2*logn) 了,比 O(n^3) 更优。

实际上,如果不对 S 进行排序而是放在哈希表中,那么复杂度就降到 O(n^2) 了。可是还有一个比较棘手的问题:如何去重以及自己和自己相加的情况。比如我们有 4 个 1,按照此办法我们会在和为 2 的位置记录多次 {1, 1} 元素对,此时我们需要对相同的元素对进行计数,否则就不能判断是不是能够 {1, 1} 和 {1, 1} 进行组合了。

 

k-Sum

推广到 K 个元素的情况。如果 K 为偶数,那么解法和 4-Sum 类似。

如果 K 为奇数,枚举第一个元素 a[i],接下来按照偶数的情况查找 s – a[i] 就好了。

N-Sum 问题”的一个响应

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s