Leetcode. Add N Sum类问题

今天无意中听到同事面试, 问到了add n sum类的问题. 想到leetcode上有很多类似的问题, 特地整理一下。

Q1: 2Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

算法

  • 用一个map保存各个元素和它对应的下标* 每遍历一个元素, 先在map中查找 target - curElement是否存在
  • 如果存在, 说明找到了一对满足要求的元素, 直接返回
  • 如果不存在, 将<当前元素, 下标>插入到map中时间复杂度是O(n), 空间复杂度是O(n)

实现

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        std::map<int, int> hashMap;
        std::vector<int> results;
        for (std::vector<int>::iterator it = nums.begin();
             it != nums.end();
             ++it)
        {
            if (hashMap.find(target - *it) != hashMap.end())
            {
                   results.push_back(hashMap[target - *it]);
                   results.push_back(it - nums.begin());
                   break;
            }
            else
            {
                   hashMap.insert(std::make_pair(*it, it - nums.begin()));
            }
        }
        return results;
    }};

Q2: 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
Find all unique triplets in the array which gives the sum of zero.Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is:
[ [-1, 0, 1], [-1, -1, 2] ]

需要注意的是, 给定的数组中, 数字是可能重复的.
基本思路和2Sum类似, 先固定一个数字a, 然后在剩下的数字里, 找到2Sum等于 -a 的两个组合.
很显然, 如果我们采用暴力列举所有组合的方法的话, 时间复杂度是O(n^3).
在我们暴力列举的时候, 一定会有很多的重复, 所以下面我们的目标就是把重复的组合过滤掉.

  1. 为了能够高效地过滤掉重复数字, 我们首先对数组排序.排序后的结果为
    [-4, -1, -1, 0, 1, 2]
    i----- h ------------p
  2. 固定下标为i的数字, 然后在h ~ p的子集中找到和为 4的组合, 方法是使用两个指针 h , p, 分别指向子数组的开头和结尾, 判断 arr[h] + arr[p]和第二目标数字(4)的大小
  • 如果 arr[h] + arr[p] > 0 - arr[i], --p 直到找到第一个和arr[h] 不相等的值
  • 如果 arr[h] + arr[p] < 0 - arr[i], ++h 直到找到第一个和arr[h] 不相等的值
  • 如果 arr[h] + arr[p] = 0 - arr[i], 说明找到了一组值, 记录下来. 然后同时更新h p直到分别找到第一个不相等的值.这三个地方的去重, 是第一个过滤重复的优化3. 找到所有arr[i]对应的组合后, ++i直到找到第一个不相等的值. 这里是第二个过滤重复的优化.排序的时间复杂度O(nlogn), 查找组合的时间复杂度是O(n^2),
    总体时间复杂度是O(n^2). 空间复杂度O(1)

实现

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        std::vector<std::vector<int> > results;
        std::sort(nums.begin(), nums.end());
        for (std::vector<int>::iterator it = nums.begin();
             it != nums.end();)
        {
            int target = 0 - *it;
            std::vector<int>::iterator head = it + 1;
            std::vector<int>::iterator tail = nums.end() - 1;
            while (head < tail)
            {
                std::vector<int> result;
                if (*head + *tail == target)
                {
                    --tail;
                    continue;
                }
                else if (*head + *tail < target)
                {
                    ++head;
                    continue;
                }
                else
                {
                    result.push_back(*it);
                    result.push_back(*head);
                    result.push_back(*tail);
                    results.push_back(result);
                   while (head < tail && *head == result[1]) ++head;
                   while (tail > head && *tail == result[2]) --tail;
                }
            }
            int curValue = *it;
            ++it;
            while (it < nums.end() && *it == curValue) ++it;
        }
           return results;
    }};

Q3: 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?
Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

算法
基本思路和3Sum类似

  • 对数组排序
  • 先固定第一个元素, 然后对其后的子数组中, 求 三个元素之和 = target - *p1, 求三元素的方法就是利用3Sum的方法. 这里不再赘述.
    时间复杂度 O(n^3), 空间复杂度 O(1).
    4Sum的实现如下
class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        std::vector<std::vector<int> > results;
        std::vector<int> result;
        result.resize(4);
        std::sort(nums.begin(), nums.end());
        for (std::vector<int>::const_iterator it1 = nums.begin();
             it1 != nums.end();)
        {
            int threeSumTarget = target - *it1;
            for (std::vector<int>::const_iterator it2 = it1 + 1;
                 it2 != nums.end();)
            {
                int twoSumTarget = threeSumTarget - *it2;
                std::vector<int>::const_iterator it3 = it2 + 1;
                std::vector<int>::const_iterator it4 = nums.end() - 1;
                while (it3 < it4)
                {
                    if (*it3 + *it4 < twoSumTarget)
                    {
                           while (++it3 < it4 && *it3 == *(it3 - 1)) continue;
                    }
                    else if (*it3 + *it4 > twoSumTarget)
                    {
                           while (--it4 > it3 && *it4 == *(it4 + 1)) continue;
                    }
                    else
                    {
                        result.clear();
                        result.push_back(*it1);
                        result.push_back(*it2);
                        result.push_back(*it3);
                        result.push_back(*it4);
                        results.push_back(result);
                        while (++it3 < it4 && *it3 == *(it3 - 1)) continue;
                        while (--it4 > it3 && *it4 == *(it4 + 1)) continue;
                    }
                   }
                   while (++it2 != nums.end() && *it2 == *(it2 - 1)) continue;
            }
            while (++it1 != nums.end() && *it1 == *(it1 - 1)) continue;
        }
        return results;
    }};

小结

Leetcode上还有一些变型的题目, 基础都是上面的三个问题.
从上面的三个问题, 我们可以推导出求xSum的方法:
即逐层固定元素, 将问题简化为求(x-1)Sum, (x-2)Sum ... 2Sum的问题.
时间复杂度为O(n^(x - 1)), 空间复杂度O(1).
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,639评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,277评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,221评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,474评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,570评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,816评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,957评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,718评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,176评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,511评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,646评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,322评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,934评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,755评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,987评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,358评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,514评论 2 348

推荐阅读更多精彩内容