【leetcode刷题】T4-3Sum Closest

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

class Solution(object):
   def threeSumClosest(self, nums, target):
       """
       :type nums: List[int]
       :type target: int
       :rtype: int
       """
       nums.sort()
       length = len(nums)
       # target2用于存储当前最接近的值，min_dis存储其与target的距离
       target2 = 0
       min_dis = sys.maxsize
       for i in range(length-2):
           # 相同元素，不再考虑
           if i > 0 and nums[i] == nums[i-1]:
               continue
           # 转换为2sum
           tmp_target = target - nums[i]
           l, r = i+1, length-1
           while l < r:
               tmp_sum = nums[l] + nums[r]
               # 等于tmp_target，不可能有距离更近的，直接返回结果
               if tmp_sum == tmp_target:
                   return target
               # 改变下标前，首先判断是否更加接近
               if abs(tmp_target - tmp_sum) < min_dis:
                   min_dis = abs(tmp_target - tmp_sum)
                   target2 = tmp_sum + nums[i]
               if tmp_sum > tmp_target:
                   r -= 1
               else:
                   l += 1
       return target2

class Solution {
public:
   int threeSumClosest(vector<int>& nums, int target) {
       //排序
       sort(nums.begin(), nums.end());
       // target2用于存储当前最接近的值，min_dis存储其与target的距离
       int target2 = 0;
       int min_dis = INT_MAX;
       bool flag = true;
       for(int i=0; flag && i < nums.size()-2; i++){
           if(i > 0 && nums[i] == nums[i-1])
               continue;
           int tmp_target = target - nums[i];
           int l=i+1, r=nums.size()-1;
           while(l < r){
               int tmp_sum = nums[l] + nums[r];
               // 等于tmp_target，不可能有距离更近的，直接返回结果
               if(tmp_sum == tmp_target){
                   target2 = target;
                   flag = false;
                   break;
               }
               // 改变下标前，首先判断是否更加接近
               if(abs(tmp_target - tmp_sum) < min_dis){
                   min_dis = abs(tmp_target - tmp_sum);
                   target2 = tmp_sum + nums[i];
               }
               if(tmp_sum > tmp_target)
                   r--;
               else
                   l++;
           }
       }
       return target2;
   }
};