N-sum问题通解

N-sum 问题还是比较典型的,这里进行一下小结。

首先描述一下 N-sum 问题:有一个数组 nums,要求从数组中选择 n 个数,使得这些数的和恰好为 target ,输出所有不重复的可行组合。

如果采用暴力解法,显然时间复杂度为 $O(N^n)$,这一般是不可取的。

下面是 N-sum 问题的LeeCode链接:

1. Two Sum

15. 3Sum

18. 4Sum

Two-Sum

先来解决Two-Sum问题,这是N-sum问题的基础。如果我们能把Two-Sum的时间复杂度降为 $O(N)$ ,然后就能把N-sum的时间复杂度降为 $O(N^{n-1})$ 了。

如果采用暴力解法,每次选择一个数时,都要遍历数组来选择另一个数,并判断和是否为 target,这样显然是低效的。当我们选择一个数 x 时,我们希望数组里有一个数为 target - x。为了快速判断数组里是否有某个数,可以用 HashSet。但是,这样存在问题,因为数组里可能有重复的数,当 x 等于 target - x 时,这种做法就错了。因此,正确的做法应该是用 HashMap,用来存储各个数还有多少可用。

双指针法

另一种解法是使用“双指针”,这种解法要求 nums 是有序的。例如,nums 为 [1, 2, 4, 7, 13, 16],target 为 15。初始时,指针p、q位于两端:

如果p、q所指向的值之和大于 target,那么q往左移,这是因为q左侧的值比q所指的值小,所以q往左移能使得之和变小;
如果之和小于 target,那么p往右移,这是因为p右侧的值比p所指的值大,所以p往右移能使得之和变大;
如果之和等于 target,那么p往右移且q往左移(有点像夹挤),这个稍微有点难理解,这也是“双指针”法的思想精髓。首先,如果p往左移或q往右移,其实就回到了之前的状态;其次,如果只是p往右移,显然之和会大于 target,如果只是q往左移,显然之和会小于 target;于是乎,p往右移且q往左移。

然后就是考虑如何判断可行组合是否重复。由于数组是有序的,可行组合的加入也是有序的,因此,只需判断当前可行组合与最后一个已加入的可行组合是否重复即可。

代码

vector<vector<int>> twoSum(vector<int>& nums, int target, int st, int ed) {
    vector<vector<int> > res;
    while (st < ed) {
        if (nums[st] + nums[ed] == target) {
            if (res.empty() || res.back()[0] != nums[st]) {
                res.push_back(vector<int>{nums[st], nums[ed]});
            }
            ++st;
            --ed;
        } else if (nums[st] + nums[ed] > target) {
            --ed;
        } else {
            ++st;
        }
    }
    return res;
}

N-Sum

问题转化

对于 N-sum 问题,外面几层其实就是暴力遍历,只有最后两个数转为 Two-Sum 问题,使用双指针法求解。这种做法,其实就相当于把时间复杂度降了一阶。

例如,对于 3-Sum 问题,先从有序数组 nums 中取一个数(遍历),然后从该数右侧的数里再取两个数(Two-Sum);对于 4-Sum 问题,先从有序数组 nums 中取两个数(遍历),然后从这两个数的右侧里再取两个数(Two-Sum)。可见,4-Sum 只是比 3-Sum 多了一层循环。为了控制循环层数,可以使用递归。

代码

vector<vector<int>> nSum(vector<int>& nums, int target, int st, int ed, int n) {
    vector<vector<int> > res;
    if (n == 2) {
        return twoSum(nums, target, st, ed);
    } else {
        for (int i=st; i<=ed; ++i) {
            int num = nums[i];
            if (res.empty() || res.back()[0] != num) {
                auto ret = nSum(nums, target-num, i+1, nums.size()-1, n-1);
                for (auto r : ret) {
                    vector<int> tmp;
                    tmp.push_back(num);
                    tmp.insert(tmp.end(), r.begin(), r.end());
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
}

“双指针”的想法还是比较巧妙的,如果没见过,还真的不容易想出来。所以,练习是有必要的,也需要进行归纳总结。

算法

上一篇 求单链表交点
下一篇 拼多多2020实习笔试题题解

添加新评论

*
*