程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 求和問題總結(leetcode 2Sum, 3Sum, 4Sum, K Sum)

求和問題總結(leetcode 2Sum, 3Sum, 4Sum, K Sum)

編輯:關於C++

(一)前言

做過leetcode的人都知道, 裡面有2sum, 3sum(closest), 4sum等問題, 這些也是面試裡面經典的問題, 考察是否能夠合理利用排序這個性質, 一步一步得到高效的算法. 經過總結, 本人覺得這些問題都可以使用一個通用的K sum求和問題加以概括消化, 這裡我們先直接給出K Sum的問題描述和算法(遞歸解法), 然後將這個一般性的方法套用到具體的K, 比如leetcode中的2Sum, 3Sum, 4Sum問題.

還有求最接近target的2、3、4個數,是上述問題的變形,思路變化不大。

(二)leetcode求和問題描述(K sum problem):

K sum的求和問題一般是這樣子描述的:給你一組N個數字(比如 vector num), 然後給你一個常數(比如 int target) ,我們的goal是在這一堆數裡面找到K個數字,使得這K個數字的和等於target。

(三)注意事項

 

注意這一組數字可能有重復項:比如 1 1 2 3 , 求3sum, 然後 target = 6, 你搜的時候可能會得到 兩組1 2 3, 1 2 3,1 來自第一個1或者第二個1, 但是結果其實只有一組,所以最後結果要去重。

去重的方法有兩個:

(1)前後移動探測,發現重復數字

 

//尋找其他可能的2個數,順帶去重  
                    while (++p < q  && num[p-1] == num[p])  
                    {  
                        //do nothing  
                    }  
                    while (--q > p && num[q+1] == num[q])  
                    {  
                        //do noghing  
                    }  

(2)借助STL容器 set:set >

 

set不允許有重復的值出現。

(四)K Sum求解方法, 適用leetcode 2Sum, 3Sum, 4Sum

方法一: 暴力,就是枚舉所有的K-subset, 那麼這樣的復雜度就是 從N選出K個,復雜度是O(N^K)


方法二: 排序+貪心

這種方法適用於2sum,3sum, 3sum cloest(找3個數的和最接近target),4sum ,4sum cloest(4個數的和最接近target)問題

總體思路:

2sum:先排序,默認非遞減排序,固定0個數,頭尾雙指針選定2個數,利用貪心策略(sum-target>0,則尾指針左移,相反頭指針右移,很容易證明),直至找到sum=target

類似於二分查找,時間復雜度O(N)

3 sum:先排序,固定1個數(外層一個for循環遍歷),再采用頭尾雙指針選定兩個數,仍然采用貪心策略移動指針,得到3sum =target

時間復雜度O(N*N)

3 sum cloest:原理同3sum,只不過多了比較,下面有代碼貼出,看一眼就明白,時間復雜度O(N*N)

4 sum:由於貪心策略只適用於雙指針,所以這裡需要固定2個數,怎麼固定?雙層for循環遍歷!!!再引入頭尾雙指針,時間復雜度O(N*N*N)

4sum cloest:同上 ,時間復雜度O(N*N*N)

 

//2 sum

int i = starting; //頭指針
int j = num.size() - 1; //尾指針
while(i < j) {
    int sum = num[i] + num[j];
    if(sum == target) {
        store num[i] and num[j] somewhere;
        if(we need only one such pair of numbers)
            break;
     otherwise
            do ++i, --j;
    }
    else if(sum < target)
        ++i;
    else
        --j;
}

//3 sum
//對原數組非遞減(遞增)排序
		InsertSort(num,num.size()); 
        
        for (int i = 0; i < num.size(); ++i)
        {
			//去重
            if (i != 0 && num[i] == num[i-1])
				continue;

            int p = i + 1, q = num.size() - 1;
            int sum = 0;
            
			//收縮法尋找第2,第3個數
            while (p < q)
            {
                sum = num[i] + num[p] + num[q];
                
                if (sum == 0)
                {
                    vector newRes;
                    newRes.push_back(num[i]);
                    newRes.push_back(num[p]);
                    newRes.push_back(num[q]);
					InsertSort(newRes,newRes.size());
                    res.push_back(newRes);

			
					//尋找其他可能的2個數,順帶去重
					while (++p < q  && num[p-1] == num[p])
					{
						//do nothing
					}
					while (--q > p && num[q+1] == num[q])
					{
						//do noghing
					}
                }
                else if (sum < 0)  //和太小,p向後移動
				{
                    ++p;
				}
                else            //和過大,q向前移動
				{
                    --q;
				}
            }
        }

// 3 sum cloest
class Solution {
public:
    int threeSumClosest(vector &num, int target) {
    int index;
    bool flag=true;
    sort(num.begin(),num.end());
        if(num.at(0)+num.at(1)+num.at(2)>target)
            index=num.at(0)+num.at(1)+num.at(2)-target ;
        else
           {
                index=target-(num.at(0)+num.at(1)+num.at(2));
                flag=false;
            }

        for (int i = 0; i < num.size(); ++i)
        {

            int p = i + 1, q = num.size() - 1;

            int sum=0;

            while (p < q)
            {
                sum = num[i] + num[p] + num[q];

                if (sum == target)
                {
                    return sum;
                }//if
                else if (sum < target)  //和太小,p向後移動
                {
                    ++p;
                    if(target-sum
//4 sum
class Solution
{
public:
    vector > fourSum(vector &num, int target) {
        // Note: The Solution object is instantiated only once.
        vector> res;
    	int numlen = num.size();
		if(num.size()<4)return res;
		
		sort(num.begin(),num.end());
		set> tmpres;
		for(int i = 0; i < numlen; i++)
		{
			for(int j = i+1; j < numlen; j++)
			{
				int begin = j+1;
				int end = numlen-1;
				while(begin < end)
				{
					int sum = num[i]+ num[j] + num[begin] + num[end];
					if(sum == target)
					{
						vector tmp;
						tmp.push_back(num[i]);
						tmp.push_back(num[j]);
						tmp.push_back(num[begin]);
						tmp.push_back(num[end]);
						tmpres.insert(tmp);
						begin++;
						end--;
					}else if(sum>::iterator it = tmpres.begin();
		for(; it != tmpres.end(); it++)
			res.push_back(*it);
		return res;
    }
};


 

 

 

 

 

 

 

 

 

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