最接近的三数之和

Similar to 3 Sum problem, use 3 pointers to point current element, next element and the last element. If the sum is less than target, it means we have to add a larger element so next element move to the next. If the sum is greater, it means we have to add a smaller element so last element move to the second last element. Keep doing this until the end. Each time compare the difference between sum and target, if it is less than minimum difference so far, then replace result with it, otherwise keep iterating.

public class Solution { public int threeSumClosest(int[] num, int target) { int result = num[0] + num[1] + num[num.length - 1];
        Arrays.sort(num);
        for (int i = 0; i < num.length - 2; i++) { int start = i + 1, end = num.length - 1; while (start < end) { int sum = num[i] + num[start] + num[end]; if (sum > target) { end--;
                } else {
                    start++;
                } if (Math.abs(sum - target) < Math.abs(result - target)) {
                    result = sum;
                }
            }
        } return result;
    }
}

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        int n = num.size();
		int result = num[0] + num[1] + num[n-1];
		sort(num.begin(),num.end());
		for(int i=0;i<n-2;i++)
		{
			int start = i + 1;
			int end = n - 1;
			while(start < end)
			{
				int sum = num[i] + num[start] + num[end];
				if(sum < target)
					start++;
				else
					end--;
				
				if(abs(sum-target) < abs(result-target))
					result = sum;
			}
		}
		return result;
    }
};

没想到太好的办法。。就这样吧
public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if(num == null || num.length < 3)
        	return 0;
        
        Arrays.sort(num);
        
        int minGap = Integer.MAX_VALUE;
        int close = 0;
        
        for(int i = 0; i < num.length - 2; i++){
        	int l = i + 1;
        	int h = num.length - 1;
        	while(l < h){
        		int gap = target - num[i] - num[l] - num[h]; 
        		if(Math.abs(gap) < minGap){
        			minGap = Math.abs(gap);
        			close = num[i] + num[l] + num[h];
        		}
        		if(gap < 0)
        			h--;
        		else if(gap > 0)
        			l++;
        		else{
        			close = num[i] + num[l] + num[h];
        			return close;
        		}
        	}
        }             
        return close;
    }
}

public class Solution {
    public int threeSumClosest(int[] num, int target) {
		int sum = 0, error = 0, result = 0, min = Integer.MAX_VALUE;
		for (int i = 0; i < num.length; i ++) {
			for (int j = i + 1; j < num.length; j ++) {
				for (int k = j + 1; k < num.length; k ++) {
					sum = num[i] + num[j] + num[k];
					error = Math.abs(sum - target);
					if(error == 0) return sum;
					if(error < min) {
						min = error;
						result = sum;
					}
				}
			}
		}
		return result;
	}
}

class Solution {
public:
    int threeSumClosest(vector<int>& num, int target) {
        sort(num.begin(), num.end());
        int tmp, appnum = INT_MAX;
        bool flag;
        for(int i = 0; i < num.size()-2; i++) {
            tmp = target - num[i];
            int k1 = i+1, k2 = num.size()-1;
            while(k1 < k2) {
                if(num[k1] + num[k2] == tmp) {
                    return target;
                }
                else if(num[k1] + num[k2] < tmp) {
                    if(appnum > tmp - (num[k1] + num[k2])) {
                        appnum = tmp - (num[k1] + num[k2]);
                        flag = 0;
                    }
                    k1++;
                }
                else {
                    if(appnum > (num[k1] + num[k2]) - tmp) {
                        appnum = (num[k1] + num[k2]) - tmp;
                        flag = 1;
                    }
                    k2--;
                }
            }
        }
        
        return flag == 0 ? target - appnum:target + appnum;
    }
};

    /*
    * 目的：找出s中和加起来的和最接近给定的目标值的三个整数
    * 方法1：回溯
    * 方法2：迭代
    */
    void getres(int index, int m, vector<int>&num,int sum, int &min, int &res,int target){
        if (m==3){
            if (abs(sum-target)<min){
                min = abs(sum-target);
                res = sum;
            }
            return;
        }
        for (int i = index; i < num.size();++i){
            getres(i+1, m+1,num,sum+num[i],min,res,target);
        }
    }
    int threeSumClosest(vector<int> &num, int target) {
        int min = INT_MAX;
        int res = 0;
        getres(0, 0, num, 0,min, res, target);
        return res;
    }
    //迭代法
    int threeSumClosest(vector<int> &num, int target) {
        int fVal=0,sVal=0,tVal =0;
        int s = 0,t = 0,sum = 0,res =num[0]+num[1]+num[2];
        sort(num.begin(),num.end());
        for (int i = 0; i < num.size()-2;++i){
            fVal=num[i];
            s = i+1;
            t=num.size()-1;
            while(s<t){
                sum = fVal+num[s]+num[t];
                if (sum<target)
                    s++;
                else if(sum>target){
                    t--;
                }
                else{
                    return sum;
                }
                if (abs(sum-target)<abs(res-target))
                    res = sum;
            }
        }
        return res;
    }

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if (nums.size() < 3)
            return -1;
        sort(nums.begin(), nums.end());
        int min_dis = INT_MAX, curr_dis;
        int threeSum, res;
        for (auto i = nums.begin(); i != nums.end() - 2;) {
            auto j = i + 1, k = nums.end() - 1;
            while (j < k) {
                threeSum = *i + *j + *k;
                curr_dis = abs(threeSum - target);
                if (curr_dis < min_dis) {
                    min_dis = curr_dis;
                    res = threeSum;
                }
                if (threeSum - target < 0)
                    while (++j < k && *j == *(j - 1));
                else if (threeSum - target > 0)
                    while (--k > j && *k == *(k + 1));
                else
                    return threeSum;
            }
            while (++i != nums.end() - 2 && *i == *(i - 1));
        }
        return res;
    }
};

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) 
    {
    int len = num.size();
    if(len<3)
        return accumulate(num.begin(),num.end(),0);
    sort(num.begin(),num.end());
    int sum = num[0]+num[1]+num[2];
    for(int i=0;i<=len-3;i++)
    {
       int j=i+1,k=len-1;
       while(j<k)
       {
            int threeSum = num[i]+num[j]+num[k];
            if(abs(sum-target) > abs(threeSum-target))   /// 更接近target
                {
                    sum = threeSum;
                    if(threeSum == target)
                        return threeSum;
                }
            else
                target > threeSum ? ++j : --k;
       }
       while(i<len-1 && num[i]==num[i+1])
         ++i;
    }
    return sum;
    }
};

import "math"
func threeSumClosest( num []int ,  target int ) int {
    // write code here
    sort.Ints(num)
    minV := math.MaxInt16
    var rs int
    for i:=0;i<len(num);i++{
        for j:=i+1;j<len(num);j++{
            for k:=j+1;k<len(num);k++{
                if tmp := num[i]+num[j]+num[k];abs(tmp,target) < minV {
                    minV = abs(tmp,target)
                    rs = tmp
                }
            }
        }
    }
    return rs
}

func abs(a, b int)int{
    if a-b > 0 {
        return a-b
    }
    return b-a
}

/**
  * 
  * @param num int整型一维数组 
  * @param target int整型 
  * @return int整型
  */
function threeSumClosest( num ,  target ) {
    // write code here
    num.sort((a,b) => a-b);//将数组从小到大排序
    let len = num.length;
    let res = num[0] + num[1] + num[len-1];//初始值设为第一个固定数加上左指针所指数和右指针所指数
    for(let i = 0; i < len-2; i++){//固定数从第一个数循环到倒数第三个数，因为当固定数为倒数第三个数时，剩下两个数分别为左右指针所指数
        let n1 = num[i];
        let left = i+1;
        let right = len-1;
        while(left < right){
            let n2 = num[left];
            let n3 = num[right];
            let sum = n1 + n2 + n3;
            if(sum == target) return sum;
            sum > target ? right--:left++;//如果三数之和大于target，右指针往左移，如果三数之和小于target，左指针往右移
            if(Math.abs(sum - target) < Math.abs(res - target)){//判断sum与target差值是否变小，变小则更新res
                res = sum;
            }
        }
    }
    return res;
}
module.exports = {
    threeSumClosest : threeSumClosest
};

class Solution {
public:
    int threeSumClosest(vector<int>& num, int target) {
        if(num.size()<3){
            return 0;
        }
        int rs=INT_MAX;
        sort(num.begin(),num.end());
        for(int i=0;i<num.size();i++){
            int l=i+1,r=num.size()-1;
            while(l<r){
                int temp=num[l]+num[r]+num[i];
                if(abs(rs-target)>abs(temp-target))
                    rs=temp;
                if(temp-target>0){
                    r--;
                }else l++;
            }
        }
        return rs;
    }
};

class Solution:
    def threeSumClosest(self , num , target ):
        # write code here
        num.sort()
        length = len(num)
        result = num[0]+num[1]+num[length-1]
        for i in range(length):
            cur = i
            start = i+1
            end = length-1
            while start < end:
                sumValue = num[cur]+num[start]+num[end]
                if abs(sumValue-target)<abs(result-target):
                    result = sumValue
                if sumValue<target:
                    start += 1
                else:
                    end -= 1
        return result

import java.util.Arrays;
import java.util.ArrayList;

public class Solution {
    ArrayList<Integer> res_list;
    int sum = 0;
    int close_temp = Integer.MAX_VALUE;
    public int threeSumClosest(int[] num, int target) {
        ArrayList<Integer> list =  new ArrayList<>();
        combine(num, target, 0, list);
        
        int result = 0;
        for(int i = 0; i < res_list.size(); i++){
            result += res_list.get(i);
        }
        return result;
    }
    //回溯法
    public void combine(int[] num, int target, int start, ArrayList<Integer> list){
        if(list.size() == 3 ){
            if(Math.abs(sum - target) < close_temp){
                close_temp = Math.abs(sum - target);
                res_list = new ArrayList<>(list);
            }
            return;
        }
            for(int i = start; i < num.length; i++){
                sum += num[i];
                list.add(num[i]);
                combine(num, target, i + 1, list);
                sum -= list.get(list.size()-1);
                list.remove(list.size()-1);
            }
    }
}

1. 首先将数组排序；
2. 分别用三个指针 lfet mid right  指向当前三个数；
3. 计算当前三个数的和，如果大于target，则left++或者（当left++>mid时）mid++;否则right--或（当right--小于mid时）mid--；
4. 当三个数的和等于target，或者left>mid或者right<mid,停止计算。

5. public int threeSumClosest (int[] num, int target) {
           // write code here
           
           if(num==null || num.length<3){
               return 0;
           }
           Arrays.sort(num);
           int left = 0;
           int right = num.length-1;
           int mid = (left+right)>>1;
           int res = 0;
           while(left<mid && mid<right){
               res = num[left]+num[mid]+num[right];
               if(num[left]+num[mid]+num[right]==target){
                   return target;
               }else if(num[left]+num[mid]+num[right]>target){
                   if(right>mid+1){
                       right--;
                   }else{
                       mid--;
                   }
               }else{
                   if(left<mid-1){
                       left++;
                   }else{
                       mid++;
                   }
               }
           }
           return res;
       }