找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1433|回复: 2
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【4 sum】【数组,Two Pointer】

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-14-2014 01:46 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
原作者 Colin
快速通道:
https://oj.leetcode.com/problems/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:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
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)


建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================



思路1:
  借鉴2 sum的思路 ,先对其进行排序,然后枚举其中的2个,剩下两个,用左右指针来判断,进行调整大小
思路2:
  完全转化为2sum,不过处理重复不用unordered_map 好麻烦

复杂度:

思路一,O(n3+nlogn)


注意细节:
1)注意要避免重复, for每层都要判断 2)左右指针 跳过重复元素时,注意边界,否则容易死循环
代码一:

  1. class Solution
  2. {
  3. public:
  4.         vector<vector<int> > fourSum( vector<int> &num,int    target   )        
  5.         {
  6.                 vector<vector<int>> ans;
  7.                 sort(num.begin(),num.end());
  8.                 int n = num.size();
  9.                 int l, r;
  10.                 for(int i = 0 ; i<n ; i ++){
  11.                   //避免重复
  12.                   if (i > 0 && num【i】 == num[i-1] )  continue;        //Ps:i > 0
  13.                   for(int j = i+1 ; j < n ; j ++)
  14.                            {
  15.                                            if (j > i + 1 && num[j] == num[j-1] ) continue;//Ps: j > i + 1  
  16.                                            l = j + 1;
  17.                                            r = n - 1;
  18.                                            while( l  < r)
  19.                                            {
  20.                                                    int sum = num【i】 + num[j] + num[l] + num[r];
  21.                                                    if (sum == target)
  22.                                                    {
  23.                                                                    vector<int> cur_ans={num【i】,num[j],num[l],num[r]};
  24.                                                                    ans.push_back(cur_ans);
  25.                                                                    do
  26.                                                                 {
  27.                                                                            l++;        
  28.                                                                 }while( l < r && num[l] == num[l-1]); //跳过这一层相等的元素
  29.                                                                    do{
  30.                                                                            r--;        
  31.                                                                 }while(l < r && num[r] == num[r + 1]);
  32.                                                                   
  33.                                                         }
  34.                                                 else  
  35.                                                 if (sum >  target)
  36.                                                         r--;
  37.                                                 else l++;
  38.                                         }
  39.                            }
  40.                 }
  41.              return ans;
  42.         }

  43. };
复制代码


相关题目:

3 sum,2 sum, 3sum closet



本帖被以下淘专辑推荐:

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-28-2014 09:33 PM | 显示全部楼层
超级版主cpcs的4 Sum总结:
http://www.meetqun.com/thread-3068-1-1.html
回复 支持 反对

使用道具 举报

3

主题

0

精华

154

积分

资深会员

Rank: 2

积分
154
发表于 12-31-2014 06:43 AM | 显示全部楼层
最近在看这个sum 这个总结很及时啊
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表