个数 else max threesum lee 次循环 变量存储 比较
题目:
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).
题解:
经过几个题的训练,基本上确定是两指针查找问题。找最接近 target 的三个数之和,第一个想法就是设两个差,一个为正,一个为负,在搜索过程中不断更新,最后比较两个差绝对值的大小,取绝对值小的差,与 target 相加即可。这里可以在循环内部跳过重复项,也可以不跳过(这样就会进行多余的若干次循环)。
Solution 1 (9ms)
- 1 class Solution {
- 2 public: 3 int threeSumClosest(vector < int > &nums, int target) {
- 4 int diffplus = INT_MAX,
- diffminus = INT_MIN + 1;
- 5 sort(nums.begin(), nums.end());
- 6 int n = nums.size();
- 7
- for (int i = 0; i2; i++) {
- 8 int j = i + 1,
- k = n - 1;
- 9 int a = nums[i];
- 10
- while (j < k) {
- 11 int b = nums[j],
- c = nums[k];
- 12
- if (a + b + c == target) 13
- return target;
- 14
- else if (a + b + c > target) {
- 15 diffplus = min(diffplus, a + b + c - target);
- 16 k--;
- 17
- }
- 18
- else {
- 19 diffminus = max(diffminus, a + b + c - target);
- 20 j++;
- 21
- }
- 22
- }
- 23
- }
- 24
- return abs(diffminus) < diffplus ? target + diffminus: target + diffplus;
- 25
- }
- 26
- };
Solution 1 中我们用了两个变量存储差,那么能不能用一个呢,那么这个 diff 只能存储差的绝对值,我们怎么知道 target 该加还是减这个 diff 呢?解决办法就是在更新 diff 时同时更新 result,在循环内时 result == a+b+c; 这样就无需 target 与 diff 的加减操作了,此时 diff 的作用只有一个:result 是否更新的条件。
Solution 2 (9ms)
- 1 class Solution {
- 2 public: 3 int threeSumClosest(vector < int > &nums, int target) {
- 4 int result = nums[0] + nums[1] + nums[2];
- 5 int diff = abs(result - target);
- 6 sort(nums.begin(), nums.end());
- 7 int n = nums.size();
- 8
- for (int i = 0; i2; i++) {
- 9 int j = i + 1,
- k = n - 1;
- 10
- while (j < k) {
- 11 int sum = nums[i] + nums[j] + nums[k];
- 12 int now_diff = abs(target - sum);
- 13
- if (now_diff == 0) return target;
- 14
- if (now_diff < diff) {
- 15 diff = now_diff;
- 16 result = sum;
- 17
- }
- 18
- else if (sum > target) k--;
- 19
- else j++;
- 20
- }
- 21
- }
- 22
- return result;
- 23
- }
- 24
- };
【LeetCode】016 3Sum Closest
来源: http://www.bubuko.com/infodetail-2026711.html