首页 > 代码库 > 【LeetCode】016 3Sum Closest

【LeetCode】016 3Sum Closest

2024-09-15 03:39:42   215人阅读

题目：

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

　　

题解：

　　经过几个题的训练，基本上确定是两指针查找问题。找最接近target的三个数之和，第一个想法就是设两个差，一个为正，一个为负，在搜索过程中不断更新，最后比较两个差绝对值的大小，取绝对值小的差，与target相加即可。这里可以在循环内部跳过重复项，也可以不跳过（这样就会进行多余的若干次循环）。

Solution 1 (9ms)

 1 class Solution {
 2 public:
 3     int threeSumClosest(vector<int>& nums, int target) {
 4         int diffplus = INT_MAX, diffminus = INT_MIN+1;
 5         sort(nums.begin(), nums.end());
 6         int n = nums.size();
 7         for(int i=0; i<n-2; i++) {
 8             int j = i + 1, k = n - 1;
 9             int a = nums[i];
10             while(j<k) {
11                 int b = nums[j], c = nums[k];
12                 if(a+b+c == target)
13                     return target;
14                 else if(a+b+c > target) {
15                     diffplus = min(diffplus, a + b + c - target);
16                     k--;
17                 }
18                 else {
19                     diffminus = max(diffminus, a + b + c - target);
20                     j++;
21                 }
22             }
23         }
24         return abs(diffminus) < diffplus? target + diffminus : target + diffplus;            
25     }
26 };

　　Solution 1 中我们用了两个变量存储差，那么能不能用一个呢，那么这个diff只能存储差的绝对值，我们怎么知道target该加还是减这个diff呢？解决办法就是在更新diff时同时更新result，在循环内时result == a+b+c;这样就无需target与diff的加减操作了，此时diff的作用只有一个：result是否更新的条件。

Solution 2 (9ms)

 1 class Solution {
 2 public:
 3     int threeSumClosest(vector<int>& nums, int target) {
 4         int result = nums[0] + nums[1] + nums[2];
 5         int diff = abs(result - target);
 6         sort(nums.begin(), nums.end());
 7         int n = nums.size();
 8         for(int i=0; i<n-2; i++) {
 9             int j = i + 1, k = n - 1;
10             while(j<k) {
11                 int sum = nums[i] + nums[j] + nums[k];
12                 int now_diff = abs(target - sum);
13                 if(now_diff == 0) return target;
14                 if(now_diff < diff) {
15                     diff = now_diff;
16                     result = sum;
17                 }
18                 else if(sum > target) k--;
19                 else j++;
20             }
21         }
22         return result;            
23     }
24 };

　　

【LeetCode】016 3Sum Closest


联系
我们