上周還在郁悶自己寫的算法由于超時沒有通過敷硅,這周就給了一個彌補的機會拷邢,難度級別“Medium”
題目:已知n個整數(shù)的數(shù)組nums挨队,給定一個數(shù)target好渠。數(shù)組S中任意三個數(shù)求和,找到其中最接近target的值步咪。保證每個輸入都對應單一解论皆。
通過上周的題再來看這道題,就很簡單了,直接代碼解說吧:
int threeSumClosest(int* nums, int numsSize, int target) {
//如果給出的數(shù)組個數(shù)少于3個,就不用比了
if (numsSize == 0) return 0;
if (numsSize == 1) return nums[0];
if (numsSize == 2) return nums[0] + nums[1];
//數(shù)據(jù)初始化,初始化的結果是前三個數(shù)字的和
int result = nums[0] + nums[1] + nums[2];
int temp = abs(result - target);
int i,j,k;
//上周我的笨算法,把所有的組合全部查一遍点晴,找出符合要求的結果
for (i = 0; i < numsSize; i++)
for (j = i+1; j < numsSize; j++) {
if (j == i) continue;
for (k = j+1; k < numsSize; k++) {
if (k == i || k == j) continue;
if (nums[i] + nums[j] + nums[k] == target) return target;
//通過比較絕對值來找出最貼近target的數(shù)
if (abs(nums[i] + nums[j] + nums[k] - target) < temp) {
result = nums[i] + nums[j] + nums[k];
temp = abs(result - target);
}
}
}
//返回結果
return result;
}
雖然這次的算法通過了感凤,但是效率還是比較低的,可以通過上周的思路粒督,先排序陪竿,然后從兩邊開始找就OK了。屠橄。族跛。