LeetCode - 16. 3Sum Closest

简介: 16. 3Sum Closest  Problem's Link  ---------------------------------------------------------------------------- Mean:  给定一个整数序列和一个目标数,在序列中找出三个数,使得这三个数的和与目标数的差最小.

16. 3Sum Closest 

Problem's Link

 ----------------------------------------------------------------------------

Mean: 

给定一个整数序列和一个目标数,在序列中找出三个数,使得这三个数的和与目标数的差最小.

analyse:

O(n^2)的做法.

如果你找到了更好的做法,请赐教^_^

Time complexity: O(N)

 

view code

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-02-17-08.50
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

class Solution
{
public :
    int threeSumClosest( vector < int >& nums , int target)
    {
        int si = nums . size();
        if( si < 3) return 0;
        if( si == 3) return ( nums [ 0 ] + nums [ 1 ] + nums [ 2 ]);
        int64_t res = INT_MAX , low , high , sum , tsum;
        sort( nums . begin (), nums . end());

        for( int i = 0; i < si; ++ i)
        {
            low = i + 1;
            high = si - 1;
            tsum = target - nums [ i ];
            while( low < high)
            {
                sum =( nums [ i ] + nums [ low ] + nums [ high ]);
                if( abs( target - res) > abs( target - sum))
                    res = sum;
                   
                if( nums [ low ] + nums [ high ] < tsum)
                    ++ low;
                else if( nums [ low ] + nums [ high ] > tsum)
                    -- high;
                else
                    return target;
            }
        }
        return ( int) res;
    }
};

int main()
{
    Solution solution;
    int n , target;
    while( cin >>n >> target)
    {
        vector < int > ve;
        for( int i = 0; i <n; ++ i)
        {
            int tmp;
            cin >> tmp;
            ve . push_back( tmp);
        }
        int ans = solution . threeSumClosest( ve , target);
        cout << ans << endl;
    }
    return 0;
}
目录
相关文章
|
算法 机器学习/深度学习
|
算法 编译器
LeetCode:658. Find K Closest Elements程序分析
好久没有练习算法了,以此纪研究生以来第一次练习算法题。 原题链接:https://leetcode.com/problems/find-k-closest-elements/description/ 题目描述:大概意思是给定一个数组[1,2,3,4,5]和两个常数k,x然后在数组中找到与x最近的的k个元素,找到后的元素依旧按照升序排列。
1723 0
|
C++
[LeetCode] Closest Binary Search Tree Value II
Problem Description: Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
1184 0
|
C++
[LeetCode] Closest Binary Search Tree Value
Problem Description: Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
903 0
[LeetCode] 3Sum Closest
This problem is very similar to 3Sum. You only need to maintain a variable for the sum that is closet to target.
756 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行