018 4Sum[M]

02-25

1 題目描述

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.

難度：Medium

2 題目樣例

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]]

3 題意分析

給定數組，尋找所有和為target的組合，也就是說[1,2,3,4]和[4,2,3,1]是同一個組合不應該在答案中出現兩次。

4 思路分析

1 暴力枚舉

先對數組排序，接著假設 $ale ble cle d$ ，然後分別遍歷 $a,b,c$ ，在剩下的數組中二分查找 $d=target-a-b-c$ ，同時利用std::set來判重。

（似乎直接四重循環更加暴力？）

代碼如下

class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int len = nums.size(); set<vector<int>> s; vector<vector<int>> ans; sort(nums.begin(), nums.end()); for(int i=0;i<len-3;i++) for(int j=i+1;j<len-2;j++) for(int k=j+1;k<len-1;k++) if(binary_search(&nums[k+1], &nums[len], target - nums[i] - nums[j] - nums[k])) s.insert({nums[i], nums[j], nums[k], target - nums[i] - nums[j] - nums[k]}); for(auto &v:s) ans.emplace_back(v); return ans; }};

排序的複雜度為 $O(nlgn)$ ，std::set::insert()的複雜度是 $O(lgn)$ ，所以時間複雜度是 $O(n^3lgn)$ ，空間複雜度不太好分析，但應該有 $Omega(1)$ ？此處存疑。

我覺得我彷彿找到了Nsum的通解！（逃

2 優化查找

還記得在3Sum的解法嗎？

沒錯我們依舊可以參考3Sum的做法，先對數組排序，接著假設 $ale ble cle d$ ，但是只遍歷 $a,b$ ，然後在剩下的數組空間里尋找所有滿足條件的 $c$ 和 $d$ 。

具體說來就是，假設 $nums[p_1]=a,nums[p_2]=b$ 且 $p_1<p_2$ ，我們不斷移動 $p_1$ 和 $p_2$ ，然後令 $p_3=p_2+1,p_4=nums.size()-1$ ，在保證的 $p_3<p_4$ 的情況下作如下循環

如果 $a+b+nums[p_3]+nums[p_4] =target$ ，說明這時滿足題意，把 $nums[p_1],nums[p_2],nums[p_3],nums[p_4]$ 加入答案，同時 $p_3$ 和 $p_4$ 分別向右和向左移動到非重複元素為止。
如果 $a+b+nums[p_3]+nums[p_4] >target$ 說明 $nums[p_4]$ 大了，需要把 $p_4$ 向左移動。
如果 $a+b+nums[p_3]+nums[p_4] <target$ 說明 $nums[p_3]$ 小了，需要把 $p_3$ 向右移動。

具體代碼如下

class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int len = nums.size(); sort(nums.begin(),nums.end()); vector<vector<int>> ans; int tp; int l; int r; for(int i=0;i<len-3;i++){ while(i<len-3&&i>0&&nums[i]==nums[i-1]) i++; for(int j=i+1;j<len-2;j++){ while(j<len-2&&j>i+1&&nums[j]==nums[j-1]) j++; l = j + 1; r = len -1; while(l<r){ tp = nums[i] + nums[j] + nums[l] + nums[r] - target; if(tp==0){ ans.push_back({nums[i], nums[j], nums[l], nums[r]}); while(l<r&&nums[l]==nums[l+1]) l++; l++; while(l<r&&nums[r]==nums[r-1]) r--; r--; } else if(tp > 0) r--; else l++; } } } return ans; }};

這裡有一個細節就是在每次循環對i和j的處理，保證了相同的元素只會被處理一次，防止出現重複組合。

整體時間複雜度 $O(n^3)$ ，空間複雜度依舊存疑。

3 進一步優化

剛才思路2中的代碼實際上還有很多情況可以優化，比如

如果 $4*nums[p_1]>target$ ，那麼顯然應該直接跳出。
如果 $nums[p_1]+3*max(nums) <target$ ，那麼顯然應該直接遍歷下一個元素。

實際上這些優化在3Sum的過程中也可以完成的，這裡我直接粘討論區的代碼了

public List<List<Integer>> fourSum(int[] nums, int target) { ArrayList<List<Integer>> res = new ArrayList<List<Integer>>(); int len = nums.length; if (nums == null || len < 4) return res; Arrays.sort(nums); int max = nums[len - 1]; if (4 * nums[0] > target || 4 * max < target) return res; int i, z; for (i = 0; i < len; i++) { z = nums[i]; if (i > 0 && z == nums[i - 1])// avoid duplicate continue; if (z + 3 * max < target) // z is too small continue; if (4 * z > target) // z is too large break; if (4 * z == target) { // z is the boundary if (i + 3 < len && nums[i + 3] == z) res.add(Arrays.asList(z, z, z, z)); break; } threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z); } return res; } /* * Find all possible distinguished three numbers adding up to the target * in sorted array nums[] between indices low and high. If there are, * add all of them into the ArrayList fourSumList, using * fourSumList.add(Arrays.asList(z1, the three numbers)) */ public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList, int z1) { if (low + 1 >= high) return; int max = nums[high]; if (3 * nums[low] > target || 3 * max < target) return; int i, z; for (i = low; i < high - 1; i++) { z = nums[i]; if (i > low && z == nums[i - 1]) // avoid duplicate continue; if (z + 2 * max < target) // z is too small continue; if (3 * z > target) // z is too large break; if (3 * z == target) { // z is the boundary if (i + 1 < high && nums[i + 2] == z) fourSumList.add(Arrays.asList(z1, z, z, z)); break; } twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z); } } /* * Find all possible distinguished two numbers adding up to the target * in sorted array nums[] between indices low and high. If there are, * add all of them into the ArrayList fourSumList, using * fourSumList.add(Arrays.asList(z1, z2, the two numbers)) */ public void twoSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList, int z1, int z2) { if (low >= high) return; if (2 * nums[low] > target || 2 * nums[high] < target) return; int i = low, j = high, sum, x; while (i < j) { sum = nums[i] + nums[j]; if (sum == target) { fourSumList.add(Arrays.asList(z1, z2, nums[i], nums[j])); x = nums[i]; while (++i < j && x == nums[i]) // avoid duplicate ; x = nums[j]; while (i < --j && x == nums[j]) // avoid duplicate ; } if (sum < target) i++; if (sum > target) j--; } return; }

複雜度相對思路2來說沒有變化，但是這些剪枝有效降低了代碼運行時間。

5 後記

從2Sum到NSum，的確是一系列相當不錯的題呢。

不知道對於NSum有沒有更好的優化方法，現在主要還是依賴查詢線性優化來讓NSum的時間複雜度降低到 $O(n^{N-1}),N>2$ 。