[Array]3 Sum 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).

方法：对数组先进行排序，然后利用Two Pointer的思想进行。时间复杂度O（n²）

class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); int sum = nums[0]+nums[1]+nums[2]; int min_diff = abs(target - sum); for(int i=0;i<nums.size()-2;i++){ int left = i+1; int right = nums.size()-1; while(left<right){ int temp_sum = nums[i]+nums[left]+nums[right]; if(temp_sum==target) return temp_sum; int temp_diff = abs(temp_sum-target); if(temp_diff<min_diff){ min_diff = temp_diff; sum = temp_sum; } if(temp_sum<target) left++; else right--; } } return sum; } };

转载于:https://www.cnblogs.com/GoFly/p/5751058.html

相关资源：JAVA上百实例源码以及开源项目