首页 > 代码库 > [Leetcode] 3Sum Closest
[Leetcode] 3Sum Closest
题目：
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.
Array
体会：
1. 这道题最直接的想法肯定是想 A3n的那种解法，就是遍历所有可能的三个数的排列，然后找结果。可是这样就是A3n = n(n-1)(n-2) = O(n3)的解法，会exceed time limit。
2. 然后就是低于3次的解法了。
class Solution { public: int threeSumClosest(vector<int> &num, int target) { // we don‘t want to change the original vector probably // how to declare vector in C++ vector<int> v(num.begin(), num.end()); int result = 0; int size = v.size(); if (size <= 3) { for (int i = 0; i < size; i++){ result += v[i]; } return result; } std::sort(v.begin(), v.end()); result = v[0] + v[1] + v[2]; int sum = 0; for (int i = 0; i < size - 2; i++) { int j = i + 1; int k = size - 1; while (j < k) { sum = v[i] + v[j] + v[k]; if (std::abs(target - sum) < std::abs(target - result)) { result = sum; if (result == target) { return result; } } if (sum > target) { k--; } else { j++; } } } return result; }};
[Leetcode] 3Sum Closest
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。