16. 3Sum Closest

素颜马尾好姑娘i 2022-04-16 01:39 176阅读 0赞

Given an array `nums` of *n* integers and an integer `target`, find three integers in `nums` such that the sum is closest to `target`. Return the sum of the three integers. You may assume that each input would have exactly one solution.

**Example:**

Given array nums = [-1, 2, 1, -4], and target = 1.
    
    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路：先排序（从小到大），然后固定一个元素，采用双指针first和last，三者的和为sum。如果sum小于target，则first++。如果sum大于target，则last--。在计算的过程中记录最小和min。

class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
          sort(nums.begin(), nums.end());                    //排序
          int min = nums[0] + nums[1] + nums[nums.size()-1]; //赋初值
          for(int i =0; i<nums.size();i++)
          {
              int first = i+1;
              int last = nums.size()-1;
    
              while(first < last)
              {
                  int sum = nums[i] + nums[first] + nums[last];
                  if(abs(sum- target) < abs(min- target))
                     min = sum;
                  if(sum == target)
                  {
                     return sum;      //此时距离最小，返回
                  }
                  else if(sum < target)
                  {
                     first++;
                  }
                  else
                  {
                      last--;
                  }
              }
          } 
            return min;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Medium - 16. 3Sum Closest

Topic Array Two Pointers Description [https://leetcode.com/problems/3sum-cl

﹏ヽ暗。殇╰゛Y/ 2023年01月01日 07:56/ 0 赞/ 131 阅读

相关 16 3Sum Closest

类似的题目有 [1 TwoSum][] [15 3Sum][] [18 4Sum][] public static int threeSumClosest

清疚/ 2022年08月10日 00:52/ 0 赞/ 53 阅读

相关 leetcode 16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to

约定不等于承诺〃/ 2022年07月29日 08:51/ 0 赞/ 156 阅读

相关 Leetcode——16. 3Sum Closest

1. 概述 1.1 题目 Given an array S of n integers, find three integers in S such that th

曾经终败给现在/ 2022年06月14日 09:26/ 0 赞/ 122 阅读

相关 leetcode 16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to

男娘i/ 2022年06月09日 07:49/ 0 赞/ 140 阅读

相关 16. 3Sum Closest

[16. 3Sum Closest ][16. 3Sum Closest] Given an array S of n integers, find t

Love The Way You Lie/ 2022年06月08日 12:48/ 0 赞/ 160 阅读

相关 3Sum Closest

[原题链接][Link 1] 给含有n个元素的数组S，寻找出S中的三个元素，使其求和接近于所给的数字，target。并且返回这三个元素之和。你应该假设每一个输出只有一个确切

「爱情、让人受尽委屈。」/ 2022年06月06日 04:44/ 0 赞/ 178 阅读

相关 Leetcode 16.3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to

港控/mmm°/ 2022年06月02日 07:44/ 0 赞/ 151 阅读

相关 16. 3Sum Closest

Given an array `nums` of n integers and an integer `target`, find three integers in `num

素颜马尾好姑娘i/ 2022年04月16日 01:39/ 0 赞/ 177 阅读

相关 Leetcode 16. 3Sum Closest

[https://leetcode.com/problems/3sum-closest/][https_leetcode.com_problems_3sum-closest]

Myth丶恋晨/ 2021年12月23日 07:27/ 0 赞/ 226 阅读