首页 > 代码库 > [LeetCode系列]3元素最近和问题的O(n^2)解法
[LeetCode系列]3元素最近和问题的O(n^2)解法
给定一个整数数组(长度不小于3) 和 一个目标值, 从数组中找出3个元素, 使得它们的和与目标值最接近, 返回这个和. 可以认为每个输入的组合都是只有唯一解的.
解法思路参考: Finding three elements in an array whose sum is closest to an given number.
我们首先将问题P转化为P‘: 能否从数组中找到3个元素, 使得它们的和最接近0?
这个转化非常简单, 只需要将原数组中的每个数都减去目标值的1/3即可.
随后我们解决P‘的方法如下:
- 使用快速排序对数组进行排序, 耗费O(nlogn)时间, 这样数组元素就从小到大排列了;
- 令 i = 0, 选取第i个元素作为基本元素, 令j = i + 1, k = n - 1, 当j < k时, 进行如下操作
- 如果num[i], num[j], num[k]的值更接近于0, 我们就更新结果;
- 如果三者的值大于0, 我们就令k = k - 1, 这样就可以选择更小的元素进行求和;
- 如果小于0, 我们令j = j + 1.
- 如果等于0, 返回0, 算法结束.
- 当 i < n - 2时, i = i + 1, 跳到第2步.
代码:
1 class Solution { 2 public: 3 int threeSumClosest(vector<int> &num, int target) { 4 int minSum = num[0] + num[1] + num[2]; 5 6 if (num.size() == 3) return minSum; 7 8 int sum = 0; 9 sort(num.begin(), num.end());10 // search for the minimal sum of continuous11 for (int i = 0; i < num.size() - 2; i++) {12 int j = i + 1;13 int k = num.size() - 1;14 while (j < k) {15 sum = num[i] + num[j] + num[k];16 if (abs(sum - target) < abs(minSum - target)) {17 minSum = sum;18 if (minSum == target) return minSum;19 }20 (sum > target)? k--: j++;21 }22 }23 return minSum;24 }25 };
[LeetCode系列]3元素最近和问题的O(n^2)解法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。