首页 > 代码库 > Leetcode#16 3Sum Closest

Leetcode#16 3Sum Closest

2024-11-23 07:28:39   202人阅读

原题地址

 

跟2Sum、3Sum、4Sum类似，都是：排序+搜索+剪枝

令sum = num[i] + num[j] + num[k] + (-target)（将-target看做一个必选的数），那这道题就跟4Sum（参见这篇文章）几乎一样了，变成了寻找最接近0的和。

需要剪枝的地方：

1. 数字太小，肯定不是最优解

2. 数字太大，肯定不是最优解

3. 数字重复

其他优化：

寻找最后一个数字可以用二分查找

 

代码：

 1 int res; 2  3 void dfs(vector<int> &num, int ans, int pos, int left) { 4   if (left == 0) { 5     if (abs(ans) < abs(res)) 6       res = ans; 7     return; 8   } 9 10   // 二分查找最后一个数11   if (left == 1) {12     int l = pos;13     int r = num.size() - 1;14     while (l <= r) {15       int m = (l + r) / 2;16       res = abs(ans + num[m]) < abs(res) ? ans + num[m] : res;17       if (ans + num[m] < 0)18         l = m + 1;19       else20         r = m - 1;21     }22     return;23   }24 25   unordered_set<int> old;26   for (int i = pos; i < num.size(); i++) {27     // 数字重复28     if (old.find(num[i]) != old.end())29       continue;30     // 数字太大31     if (num[i] * left + ans > abs(res))32       break;33     // 数字太小34     if (num[num.size() - 1] * (left - 1) + num[i] + ans < -abs(res))35       continue;36     old.insert(num[i]);37     dfs(num, ans + num[i], i + 1, left - 1);38   }39 }40 41 int threeSumClosest(vector<int> &num, int target) {42   sort(num.begin(), num.end());43   res = num[0] + num[1] + num[2] - target;44   dfs(num, -target, 0, 3);45   return res + target;46 }

 

Leetcode#16 3Sum Closest


联系
我们