找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[米群网刷题小分队] 【LeetCode小分队】【3 Sum Closest】【数组,排序】-【刷题第一弹】

[复制链接]

23

主题

16

精华

1207

积分

顶级会员

Rank: 6Rank: 6

积分
1207

推广达人宣传达人突出贡献

发表于 11-5-2014 12:30 PM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 MengMa 于 12-28-2014 09:34 PM 编辑

快速通道:
https://oj.leetcode.com/problems/3sum-closest/

题目:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).


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



思路:
        先排序,然后 双指针前后扫,根据与当前sum的大小来判断前后指针的移动。
        注意每次判断之前都要与当前最优diff比较。

复杂度:
        O(n2)
细节:
         注意每次判断之前都要与当前最优diff比较。
代码:

  1. class Solution
  2. {
  3. public:
  4.         int threeSumClosest(vector<int> &num, int target){
  5.                 int n = num.size();
  6.                 int l,r,sum;
  7.                 int diff= INT_MAX,ans;
  8.                 sort(num.begin(),num.end());
  9.                 for(int i = 0 ; i < n ; i ++){
  10.                         if (i>0 && num【i】 == num[i-1]) continue;
  11.                         l = i + 1;
  12.                         r = n - 1;
  13.                         while(l < r)
  14.                         {
  15.                                 sum = num【i】 + num[l] + num[r];
  16.                                 if(abs(sum - target) <diff) //每次都判断
  17.                                   {
  18.                                                    ans = sum;
  19.                                                 diff =  abs(sum - target);
  20.                                   }
  21.                                   else
  22.                                           if (sum<target)
  23.                                                   l++;
  24.                                           else
  25.                                                   r--;                                
  26.                         }
  27.                 }
  28.                 return ans;
  29.                 }        
  30. };
复制代码

相似:
2 sum,4sum

本帖被以下淘专辑推荐:

发表于 11-8-2014 05:27 PM | 显示全部楼层
其实我想过一个办法可以减小时间复杂度。但是实现起来非常困难。
按照3SUM的办法去找,其实最接近的只有当上一次的sum,preSum > target && curSum < target的时候,这两个才有可能会是最接近的。因为其他的要么大于pre,要么小于cur,不可能比这两个中最接近的那个更接近。这样就可以不用每次都和diff比较,而且当提前出现正负变化的时候,left和right的指针也不用继续移动,直接到下一个i。
不过这种需要克服当preSum一直大于或者一直小于target的情况,这一点最为麻烦
回复 支持 反对

使用道具 举报

4

主题

1

精华

316

积分

高级会员

Rank: 3Rank: 3

积分
316
发表于 11-8-2014 09:03 PM | 显示全部楼层
我做此题和楼主思路一样,对于4sum也有了这个思维,发现leetcode上速度比用hashtable方法做出来的还快些
回复 支持 反对

使用道具 举报

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

本版积分规则

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