[LeetCode] 3Sum Closest
LeetCode Closest
2023-09-11 14:17:25 时间
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 一样,但不用去重,
1 class Solution { 2 public: 3 int threeSumClosest(vector<int> &num, int target) { 4 5 int n = num.size(); 6 7 sort(num.begin(), num.end()); 8 9 10 int a, b,c; 11 int min_gap = INT_MAX; 12 int ret = 0; 13 14 for(int a = 0; a < n-2; a++) 15 { 16 b = a +1; 17 c = n-1; 18 19 while(b < c) 20 { 21 int sum = num[a] + num[b] + num[c]; 22 int gap = abs(sum - target) ; 23 if(gap < min_gap) 24 { 25 min_gap = gap; 26 ret = sum; 27 } 28 29 if(sum < target) 30 b++; 31 else if(sum > target) 32 c--; 33 else 34 return target; 35 } 36 } 37 38 return ret; 39 40 } 41 };
相关文章
- LeetCode 的回溯算法题目用这个模板解题,一网打尽,so easy!!!
- Leetcode: Unique Word Abbreviation
- Leetcode: Walls and Gates
- LeetCode高频题73. 矩阵置零
- 98、【树与二叉树】leetcode ——112. 路径总和:5行精简代码回溯法[带剪枝]+迭代法(C++版本)
- 60、【数组】leetcode——904. 水果成篮-滑动窗口:最大窗口(C++版本)
- 【LeetCode】122. Best Time to Buy and Sell Stock II
- 【LeetCode】141. Linked List Cycle (2 solutions)
- [LeetCode] 1109. Corporate Flight Bookings 公司航班预订
- [LeetCode] 776. Split BST 分割二叉搜索树
- [LeetCode] 518. Coin Change 2 硬币找零之二
- [LeetCode] Design In-Memory File System 设计内存文件系统
- [LeetCode] 438. Find All Anagrams in a String 找出字符串中所有的变位词
- [LeetCode] 270. Closest Binary Search Tree Value 最近的二分搜索树的值
- [LeetCode] Basic Calculator 基本计算器
- [LeetCode] 16. 3Sum Closest 最近三数之和