程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [leetcode] 16 3Sum Closest(數組)

[leetcode] 16 3Sum Closest(數組)

編輯:C++入門知識

[leetcode] 16 3Sum Closest(數組)


暴力循環的時間復雜度是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

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved