暴力循環的時間復雜度是O(N^3),肯定是不可取的。我們要充分利用題目中的條件進行分析,如何才能相對高效的比較數組中指定個數元素的和 和target的大小呢?
我們可以先對數組進行排序,如果是計算兩個元素的和的話,我們會分別設置頭和尾兩個指針,向中間靠攏,那麼三個的話,我們只需要先對第一個數進行循環取值下標i,剩下的兩個指針分別指向i+1和數組的最後一個元素,這樣的復雜度是 排序O(nlogn) + 查找O(n^2) = O(n^2)。
注:不要sum>target就 return,也許在下一個循環中還會有合適的。
class Solution { public: int threeSumClosest(vector& nums, int target) { int ans,k,sum,j; sort(nums.begin(),nums.end()); int flag=0; for(int i=0;i