首页 > 代码库 > [LeetCode] 3Sum Closest

[LeetCode] 3Sum Closest

2024-07-08 16:56:09   217人阅读

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).

分析：

同3sum 一样，但不用去重，

 1 class Solution { 2 public: 3     int threeSumClosest(vector<int> &num, int target) { 4          5         int n =  num.size(); 6          7         sort(num.begin(), num.end()); 8          9         10         int a, b,c;11         int min_gap = INT_MAX;12         int ret = 0;13                 14         for(int a = 0; a < n-2; a++)15         {16             b = a +1;17             c = n-1;18             19             while(b < c)20             {21                 int sum = num[a] + num[b] + num[c];22                 int gap = abs(sum - target) ;23                 if(gap < min_gap)24                 {25                     min_gap = gap;26                     ret = sum;27                 }28                 29                if(sum < target)30                     b++;31                 else if(sum > target)32                     c--;33                 else34                     return target;35             }36         }37         38         return ret;39         40     }41 };

 


联系
我们