• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • LeetCode 4Sum

    Given an arraySofnintegers, are there elementsa,b,c, anddinSsuch thata+b+c+d= target? Find all unique quadruplets in the array which gives the sum of target.

    Note:

    • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie,abcd)
    • The solution set must not contain duplicate quadruplets.

        For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
    
        A solution set is:
        (-1,  0, 0, 1)
        (-2, -1, 1, 2)
        (-2,  0, 0, 2)

    這道題和3Sum的思路是一樣的。時間復雜度是O(n^3),增加了一個外循環判斷,程序長了點,總的程序結構也是一樣的。

    #include<iostream>
    #include<vector>
    #include<string>
    #include<algorithm>
    
    using namespace std;
    
    class Solution {
    public:
    	vector<vector<int> > fourSum(vector<int> &num, int target) 
    	{
    		vector<vector<int> > result;
    		if (num.size() < 4)
    		{
    			return result;
    		}
    		vector<int> fNum(4);
    		sort(num.begin(), num.end());
    
    		int i = 0, j = 0, k = 0, r = num.size()-1;
    		while (i < r-2)
    		{
    			for (j = i+1; j < r-1;)
    			{
    				//Notice: don't forget to reset the value of r = num.size()-1;
    				for (k = j+1, r = num.size()-1; k < r; )
    				{
    					int temp = num[i] + num[j] + num[k] + num[r];
    					if (temp == target)
    					{
    						fNum[0] = num[i]; fNum[1] = num[j]; fNum[2] = num[k]; fNum[3] = num[r];
    						result.push_back(fNum);
    						k++; r--;
    						//注意判斷重復的時候需要放進判斷條件括號里面,因為沒有移動的時候不需要判斷
    						//k和r都不一定每次移動的
    						while (k<r && num[k] == num[k-1])
    						{
    							k++;
    						}
    						while (k<r && num[r] == num[r+1])
    						{
    							r--;
    						}
    					}
    					else if (temp < target)
    					{
    						k++;
    						while (k<r && num[k] == num[k-1])
    						{
    							k++;
    						}
    					}
    					else
    					{
    						r--;
    						while (k<r && num[r] == num[r+1])
    						{
    							r--;
    						}
    					}
    
    				}
    				j++;
    				while (j<r-1 && num[j] == num[j-1])
    				{
    					j++;
    				}
    			}
    			i++;
    			while (i<r-2 && num[i] == num[i-1])
    			{
    				i++;
    			}
    		}
    		return result;
    	}
    };
    int main() 
    {
    	int a[] = {2,7,9,5,5,3,8,10,-1,-2,-5,-6,-17,-35};
    	int len = sizeof(a)/sizeof(int);
    	vector<int> vi(a, a+len);
    	cout<<"The array is:\n";
    	for (auto x:vi)
    		cout<<x<<" ";
    	cout<<endl;
    
    	Solution solu;
    	vector<vector<int> > vt = solu.fourSum(vi, 10);
    
    	for (auto x:vi)
    		cout<<x<<" ";
    	cout<<endl;
    	for (auto x:vt)
    	{
    		for (auto y:x)
    			cout<<y<<" ";
    		cout<<endl;
    	}
    
    	system("pause");
    	return 0;
    }
    


    版權聲明:本文為iteye_2829原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/iteye_2829/article/details/82551003

    智能推薦

    LeetCode 454: 四數相加 II 4Sum II

    題目: 給定四個包含整數的數組列表 A , B , C , D ,計算有多少個元組 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 為了使問題簡單化,所有的 A, B, C, D 具有相同的長度 N,且 0 ≤ N ≤ 500 。所有整數的范圍在 -228 到 228 - 1 之間,最終結果不會超過 231 - 1 。 Given fou...

    【leetcode】454. 4Sum II 總結

    【方法一】 「思路」 近似暴力解法,將AB數組中元素依次相加得到數組ab,CD數組中元素依次相加得到數組cd,若ab中的元素加cd中的元素和為0,則結果加1. 「結果」 Time Limit Exceeded 「代碼」 【方法二】 「思路」 同樣將數組其分為兩組,用map的代替for的兩重循環。 「結果」 Runtime: 1278 ms 「代碼」 【方法三】 「思路」 同樣將數組分為兩組A+B和...

    算法作業HW21:LeetCode 18 4Sum

    Description: Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d&nb...

    LeetCode 454. 4Sum II ***** 靈活的設定鍵

    題目 題意 注意 思路 代碼 結果 區別于184Sum 題目 Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero. To make problem a bit easier, ...

    leetcode454. 4Sum II四個數之和

    題意 454. 4Sum II Medium Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero. To make problem a bit easier, all A, B...

    猜你喜歡

    hive 導出數據之一列多行,轉為一行多列

    需求:提取數據 說明:原數據是一列多行,需要轉化為一行多列 待查詢表為:temp_05 待查詢數據為: 待查詢數據如圖: 需要提取的數據表頭如下: 預定日期 昨日價格 前天價格 2018-02-01 2018-02-02 2018-02-03 2018-02-04 可用提數 SQL 數據如圖: 以下為嘗試過程 數據如圖: 數據如圖: 數據如圖: 數據如圖:...

    asp.net做一個簡易的聊天室

    要求: 結果: 關鍵代碼: Default.aspx Default.aspx.cs Default2.aspx Default2.aspx.cs Default3.aspx Default3.aspx.cs Default4.aspx...

    動態SQL和多表關聯-筆記

    《動態SQL與多表關聯》筆記 學習目標 能夠使用動態SQL完成SQL拼接 能夠使用resultMap完成多表查詢 能夠使用一對一查詢 能夠使用一對多查詢 (注:多對多其實就是兩個一個多) 映射文件:為什么要resultMap 目標 定義結果映射 使用結果映射 回顧 在mybatis中有2種配置文件: 核心配置文件,如:sqlMapConfig.xml 實體類映射文件,如:UserMapper.xm...

    【OpenGL C++ UE4】獲取模型頂點及面索引數據,并優化存儲結構供UE4繪制

    目錄 一、功能需求 二、成果 三、環境配置 四、詳細步驟 4.1 Max制作三棱錐并處理 4.2 核心代碼 4.2.1 傳入結構體數據 4.2.2 頂點去重、更新索引 4.2.3 輸出本地CSV文件 4.3 UE4繪制 一、功能需求 想必你肯定會問我一個問題,UE4直接導入模型不好么? 哈哈,前提是在做畢設時,導師提供的只有頂點與面索引數據,沒有模型。 下文詳細介紹了畢設開發中的難點,涉...

    解決Pyinstaller打包numpy和pandas庫文件過大問題

    解決Pyinstaller壓縮numpy和pandas庫文件過大問題 文件包類型和網上的方法 Windows下docker的安裝 在docker下實現打包     今天是2021年的第一天,先祝各位小伙伴現年快樂哈。最近因為做了一個項目,需要打包文件,文件中包含了numpy和pandas庫,結果打包出來幾百行的代碼居然要900m,人都傻了,翻遍了全網找解決方...

    精品国产乱码久久久久久蜜桃不卡