首页 > 代码库 > leetcode:3sum closet
leetcode:3sum closet
题目:给一个数组和给定的目标值,要求在数组里找出三个元素,这三个元素的和最接近目标值,当然等于是最好的。
用3sum的方法,把判定条件作些修改。
int twoSum(vector<int> &num, int start, int target) { if(num.size() < 3 || start >= num.size()) return -target; int head = start; int tail = num.size() - 1; int result = -target; int erro = 0x7fffffff; while (head < tail) { int sum = num[head] + num[tail]; if(sum == target) { result = target; return target; } else if(sum < target){ do { ++head; } while (head < tail && num[head] == num[head - 1]); } else { do { --tail; } while (tail > head && num[tail] == num[tail + 1]); } int curerro = abs(sum - target); if(curerro < erro) { result = sum; erro = curerro; } } return result; } int threeSumClosest(vector<int> &num, int target) { const int len = num.size(); if(len < 3) return 0; sort(num.begin(), num.end()); int closet = -target; int erro = 0x7fffffff; for (int i = 0; i < len - 2; ++i) { int thisloop = twoSum(num, i + 1, target - num[i]); if(thisloop == target - num[i]) return target; int cur_erro = abs(thisloop + num[i] - target); if(cur_erro < erro) { closet = thisloop + num[i]; erro = cur_erro; } while(i + 1 < len && num[i + 1] == num[i]) ++i; } return closet; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。