程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 筆試題31. LeetCode OJ (18)

筆試題31. LeetCode OJ (18)

編輯:C++入門知識

筆試題31. LeetCode OJ (18)


\

如果說求兩個數相加是輕松,那麼求三個數相加則是痛苦,如果說求四個數相加呢-----絕望。

沒錯,拿到這個題的時候確實有些絕望,但是既然開發這個題的人如此刁難我們,我們也不能放棄,不要辜負別人的一番好意,所以我咬牙繼續。

經歷過前面的風雨,我們也學會了成長,這道題是建立在前面的題的基礎上而開始的。題目的要求比較嚴格,要求四個數的和和target的值相等,且四個數字不重復且升序。

所以我們得一個一個的去試探,也就是遍歷,這個應該得循環嵌套的遍歷,因為我們不能放過每一種情況,因為它可能在包含在我們要求的情況中。思路其實不難,代碼如下:

 

class Solution {
public:
	vector> fourSum(vector& nums, int target) {
		vector > last;
		int len = nums.size();
		if (len < 4)
		{
			return last;
		}
		//1.排序
		sort(nums.begin(), nums.end());
		//遍歷
		//特殊處理一下,若最小的四個數的和比target還大或者最大的四個數的和比target還大,那麼我們直接退出
		if (nums[len - 1] + nums[len - 2] + nums[len - 3] + nums[len - 4] < target)
		{
			return last;
		}
		if (nums[0] + nums[1] + nums[2] + nums[3] > target)
		{
			return last;
		}
        //循環遍歷,不能重復,那麼必須得一個一個的試,因為排序了,所以情況的復雜性減少了很多
		for (int i = 0; i < len - 3; ++i)
		{ //1層
			while (i > 0 && nums[i] == nums[i - 1])
			{//處理重復數字,但是第一次遍歷到的時候不能處理掉,否則可能錯過一些解
				++i;
			}
			for (int j = i + 1; j i + 1 && nums[j] == nums[j - 1])
				{//處理重復數字,但是第一次遍歷到的時候不能處理掉,否則可能錯過一些解
					++j;
				}
				int pos1 = j + 1;
				while (pos1 < len - 1)
				{ //3層
					while (pos1>j + 1 && nums[pos1] == nums[pos1 - 1])
					{//處理重復數字,但是第一次遍歷到的時候不能處理掉,否則可能錯過一些解
						++pos1;
					}
					int pos2 = pos1 + 1;
					while (pos2 < len && nums[i] + nums[j] + nums[pos1] + nums[pos2] < target)
					{
						++pos2;
					}
					if (pos2 == len)
					{
						++pos1;
						continue;
					}
					if (nums[i] + nums[j] + nums[pos1] + nums[pos2] == target)
					{
						vector tmp;
						tmp.push_back(nums[i]);
						tmp.push_back(nums[j]);
						tmp.push_back(nums[pos1]);
						tmp.push_back(nums[pos2]);
						last.push_back(tmp);
						++pos1;
						continue;
					}
					if (nums[i] + nums[j] + nums[pos1] + nums[pos2] > target)
					{//
						++pos1;
						continue;
					}
				}
			}
		}
		return last;
	}
};
我總結了一下這類題的做法,不要被題目所嚇倒,你要相信,前面有很多人作對過,所以我們也是可以作對的,我的代碼是正確的,是經過平台測試的,測試結果如下:

 

\
 

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