LeetCode 18. 4Sum and LeetCode 454. 4Sum II

【题目 LeetCode 18】

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.

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

【题解】

本题的思路如下： 

1、对数组排序 2、确定四元数中的前两个（a，b） 3、遍历剩余数组确定两外两个（c，d），确定cd时思路跟3Sum确定后两个数据一样，二分查找左右逼近。 4、在去重时采用set集合

【代码】

vector<vector<int>> fourSum(vector<int>& nums, int target) { int start,end; int nSize = nums.size(); vector<int> triplet; vector<vector<int>> triplets; set<vector<int>> sets; sort(nums.begin(),nums.end()); for(int i = 0;i < nSize - 3;i++){ for(int j = i + 1;j < nSize - 2;j++){ //二分查找 start = j + 1; end = nSize - 1; while(start < end){ int curSum = nums[i] + nums[j] + nums[start] + nums[end]; if(target == curSum){ triplet.clear(); triplet.push_back(nums[i]); triplet.push_back(nums[j]); triplet.push_back(nums[start]); triplet.push_back(nums[end]); sets.insert(triplet); start++; end--; } else if (target > curSum) start ++; else end --; } } } set<vector<int>>::iterator it; for(it = sets.begin(); it != sets.end(); it++) triplets.push_back(*it); return triplets; }

【题目 LeetCode 454】

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, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] Output: 2 Explanation: The two tuples are: 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0 【题解】 本题的难度相对于LeetCode 18来说，简单了不少，思路如下：

1、先确定前两个数组元素的和，并用map保存key值(和)和value(两个数组元素的和相同的个数)

2、接着计算后两个数组的元素的和的负数，如果和前两个数组元素的和相等，证明四个数组的和值为0

【代码】

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) { int nResult = 0; map<int, int> Match; int nSize = A.size(); for (int i = 0; i < nSize; i++) { for (int j = 0; j < nSize; j++) { int nSum = A[i] + B[j]; if (Match.find(nSum) == Match.end()) Match.insert(pair<int, int>(nSum, 0)); Match[nSum] += 1; } } for (int i = 0; i < nSize; i++) { for (int j = 0; j < nSize; j++) { int nSum = -(C[i] + D[j]); if (Match.find(nSum) != Match.end()) nResult += Match[nSum]; } } return nResult; }