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