首页 > 代码库 > [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.
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一样,不能用O(n^3)遍历,需要有一些可以简化的步骤,三层遍历肯定Time Limited Exceeded!
class Solution {public: int threeSumClosest(vector<int> &num, int target) { int n = num.size(); map<int,int> diff;//key是target和sum的差值的绝对值,value是sum值 sort(num.begin(),num.end()); int sum ; for(int i=1;i<n-1;i++){ int l = 0, r= n-1; while(l<i && r>i){ if(l>1 && num[l] == num[l-1]){ l++; continue; } if(r<n-1 && num[r] == num[r+1]){ r--; continue; } sum = num[l]+num[i]+num[r]; if(sum == target) return sum; else { int abs = sum-target>0 ? sum-target :target-sum; diff[abs] = sum; if(sum >target) r--; else l++; } }//end while }//end for map<int,int>::iterator iter = diff.begin(); return (*iter).second; }};
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。