LeetCode Online Judge 题目C# 练习 - 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).

 1         public static int threeSumClosest(int[] S, int target)
 2         {
 3             Array.Sort(S);
 4             int Min = Int32.MaxValue;
 5             int sum = Int32.MinValue;
 6             for (int a = 0; a <= S.Length - 2; a++)
 7             {
 8                 int b = a + 1;
 9                 int c = S.GetUpperBound(0);
10                 while (b < c)
11                 {
12                     sum = S[a] + S[b] + S[c];
13                     if (target == sum)
14                     {
15                         //once we found sum = target, return.
16                         return sum;
17                     }
18                     else
19                     {
20                         if (Math.Abs(target - sum) < Min)
21                         {
22                             Min = Math.Abs(target - sum);
23                         }
24                         if (target > sum)
25                             b++;
26                         else
27                             c--;
28                     }
29                 }
30             }
31             return sum;
32         }

代码分析：

　　这一题的方法跟上一题 3SUM 的方法相似，a 从 0 到 S.Length - 3, b 从 a + 1 , c 从 S.Length - 1 各自往中间靠。时间复杂度为O(n²)。

　　代码一看就明白。值得一提的是GetUpperBound(0) 这个方法，它返回的是数组第一维的上界，如果是一维数组的话，结果等于Length - 1。之前看的一本讲C#数据结构与算法的书，里面基本上都用这个方法获取数组上界，我也不清楚是不是有什么原因，请各位指教。