LeetCode -- 3Sum Closest

LeetCode -- 3Sum Closest

題目描述：
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).


本題與 Three Sum Zero類似，不同點在於，之前是尋找a+b+c=0的組合，現在是找最接近target的a+b+c的值。


思路：
依然是two pointer的思路。
1.對數組排序
2.使用a表示當前第i輪查找，b=i+1，表示第i輪的第1個元素，b∈[i+1,n)，c=len-1，一開始指向最後一個元素。
3.當找到a+b+c=target，直接返回；如果a+b+c < target，b++；否則，c--。
4.每次取Math.Abs(a+b+c- target)與當前Math.Abs(min-target)的最小值。
5.最後返回min




實現代碼：

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) 
    {
        if(nums == null || nums.Length < 3){
    		return nums.Sum();
    	}
    	
    	var list = nums.OrderBy(x=>x).ToList();
    	
    	var len = list.Count;
    	
    	int? min = null;
    	
    	for (var i = 0 ;i <= len - 3 ;i++)
    	{
    		var a = list[i];
    		var start = i+1;
    		var end = len-1;
    		while (start < end) 
    		{
    			var b = list[start];
    			var c = list[end];
    			if(a+b+c == target){
    				min = target;
    				break;
    			}
    			else if (a+b+c > target){
    				end --;
    			}
    			else{
    				start ++;
    			}
    			// update min
    			if (min == null || Math.Abs(a+b+c - target) < Math.Abs(min.Value - target)) 
    			{
    				min = a+b+c;
    			}
    		}
    	}
    	
    	return min.Value;
    }
}