Leetcode16. 最接近的三数之和

Every day a Leetcode

题目来源：16. 最接近的三数之和

解法1：排序 + 双指针

对数组 nums 进行排序。

枚举 nums[i]，在区间 (i, n - 1] 内使用双指针 l、r，维护 res = nums[i] + nums[l] + nums[r] 与 target 最接近的值。

代码：

class Solution
{
public:int threeSumClosest(vector<int> &nums, int target){int n = nums.size();int ans = nums[0] + nums[1] + nums[2];sort(nums.begin(), nums.end());for (int i = 0; i < n; i++){int l = i + 1, r = n - 1;while (l < r){int sum = nums[i] + nums[l] + nums[r];if (sum == target)return sum;if (abs(sum - target) < abs(ans - target))ans = sum;if (sum < target)l++;elser--;}}return ans;}
};

结果：

复杂度分析：

时间复杂度：O(n²)，其中 n 是数组 nums 的长度。我们首先需要 O(nlogn) 的时间对数组进行排序，随后在枚举的过程中，使用一重循环 O(n) 枚举 a，双指针 O(n) 枚举 b 和 c，故一共是 O(n²)。

空间复杂度：O(logn)，其中 n 是数组 nums 的长度。