首页 > 代码库 > 【LeetCode】 16. 3Sum Closest 解题小结
【LeetCode】 16. 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.
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).这个题目应该说是上一题 3Sum的一般化，因为题目说明输入中肯定能有一个解，初始化sum就前三个元素就好了。查找方式和3Sum一样，不过判断的时候，如果sum = target，那么就可以直接返回了。如果sum到target的距离小，那么最小和更新，否则根据Sum在target左边还是右边分别left++或right--。
class Solution {public: int threeSumClosest(vector<int>& nums, int target) { if(nums.size() < 3) return 0; sort(nums.begin(), nums.end()); int minT = nums[0]+nums[1]+nums[2]; for(int i = 0 ; i < nums.size()-2; ++i){ if (i > 0 && nums[i] == nums[i-1])continue; int a = nums[i]; int left = i+1; int right = nums.size()-1; while(left < right){ int b = nums[left]; int c = nums[right]; if (a+b+c-target == 0) { minT = a+b+c; return minT; } if (abs(a+b+c-target) < abs(minT-target)){ minT = a+b+c; } if (a+b+c-target < 0){ left++; } if (a+b+c-target > 0){ right--; } } } return minT; }};
【LeetCode】 16. 3Sum Closest 解题小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。