The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
解：
一開始自己試的，把所有滿足的都放到了一個vector裡
#include
#include
using namespace std;
vector threeSum(vector &num) {
vector::iterator r1;
vector::iterator r2;
const int target = 0;
vector result;
for (r1 = num.begin(); r1 != num.end(); ++r1)
{
int a = *r1;
for (r2 = r1 + 1; r2 != num.end(); ++r2)
{
int b = *r2;
int c = target - a - b; //找第三個數時可以用二分法等來縮短時間復雜度，前兩個是就這樣了，n^2,第三個可logn
，後來查的，注意find不是成員函數，是STL算法,返回位置，二分法是binary_find(起位置，終位置，要查找的值);也是算法，但返回是bool
vector::const_iterator r3 = find(r2 + 1, num.end(), c);
if (r3 != num.end())
{
result.push_back(a);
cout << " a: " << a;
result.push_back(b);
cout << " b: " << b;
result.push_back(c);
cout << " c: " << c;
cout << endl;
}
}
}
return result;
}
int main()
{
vector a;
a.push_back(1);
a.push_back(-4);
a.push_back(0);
a.push_back(4);
a.push_back(-1);
a.push_back(5);
a.push_back(5);
vector resultr;
vector::iterator rp;
resultr = threeSum(a);
for (rp = resultr.begin(); rp != resultr.end(); ++rp)
cout << " " << *rp;
cout << endl;
}
由此算法改成vector數組存放到vector，提交結果是Output Limit Exceeded
class Solution {
public:
vector > threeSum(vector &num) {
vector::iterator r1;
vector::iterator r2;
const int target = 0;
vector> result;
for (r1 = num.begin(); r1 != num.end(); ++r1)
{
int a = *r1;
for (r2 = r1 + 1; r2 != num.end(); ++r2)
{
int b = *r2;
int c = target - a - b;
if (binary_search(r2 + 1, num.end(), c))
{
result.push_back(vector {a,b,c});
}
}
}
return result;
}
};
後來發現沒考慮數組元素少於3的情況，和用二分法之前需要對其進行排序，更正後還是Output Limit Exceeded，後又查到for循環的判斷條件1：-2； 2： -1 ；,後來找到原因，是我的算法不能排除重復的三個數，比如0，0，0，0，會出現好多組{0，0，0}，而題目要求不能，後來想到第二個for中加個一個if(r2 == prev(r2)) continue;這樣首先r2第一個元素時不行，另外對r1的考慮也不健全（如 -1，-1，-1，2還是會有重復），後來還是采用答案中那種，把++r1換成了r1 = upper_bound(r1,prev(num.end(),2),*r1)，++r2換成r2 = upper_bound(r2,prev(num.end()),*r2)後就AC了。既然找到問題所在，那麼我那個思路也是應該可行的，只是注意對特殊邊界的處理，這裡是第一個，所以改成這個版本後就AC了哈哈（一開始沒AC是馬虎了，r2寫r1）。（注意這種排除重復的滿足條件的三個數的前提是排好序了）
vector> threeSum(vector &num) {
vector::iterator r1;
vector::iterator r2;
const int target = 0;
vector> result;
if (num.size() < 3) return result;
sort(num.begin(),num.end());
for (r1 = num.begin(); r1 < prev(num.end(), 2); ++r1)
{
if (r1 > num.begin()&&(*r1 == *prev(r1))) continue;
//這裡注意順序，先保證不是第一個，再進行prev,原本用了兩個連if，覺得太不規范了， 但是Run Time 卻從288到了328ms,難道 if (r1 > num.begin()) if((*r1 == *prev(r1))) continue;比 &&快？
int a = *r1;
for (r2 = r1 + 1; r2 < prev(num.end(), 1); ++r2)
{
if (r2 > r1 + 1 && (*r2 == *prev(r2))) continue;
int b = *r2;
int c = target - a - b;
if (binary_search(r2 + 1, num.end(), c))
{
result.push_back(vector {a,b,c});
}
}
}
return result;
}
3.
3Sum Closest
Total Accepted: 21058 Total Submissions: 78146My
Submissions
Given an array S of n integers, find three integers in S such
that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
分析： 與上題的不同，上題是等於，這題是接近，看似還是兩個循環，再第三個再用循環把最近的找出來就行，可是這樣時間復雜度n^3
再分析，與上個題不同的是，上個提相當於1+1+1 三個部分，這個題相當於1+ 2兩個部分，把後兩個數的和看成一個整體
這樣思路就出來了，先排序，然後選一個數，剩下兩個左右夾逼（因已經排好序，比要求大就後面的前移，小就前面的後移）時間復雜度n^2,空間復雜度O（1）(是不是對空間來說，沒開辟新的數組在存原數組就是1哈哈)（補：算法的空間復雜度一般也以數量級的形式給出。如當一個算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)；當一個算法的空間復雜度與以2為底的n的對數成正比時，可表示為O(log2n)；當一個算法的空間復雜度與n成線性比例關系時，可表示為O(n)）
int threeSumClosest(vector &num, int target) {
int result = 0;
int min_gap = INT_MAX;
sort(num.begin(),num.end());
for(auto a = num.begin(); a != prev(num.end(),2); a = upper_bound(a,prev(num.end(),2),*a))
{
auto b = next(a);
auto c = prev(num.end());
while (b < c)
{
int sum = *a + *b + *c;
int gap = abs(sum - target);
if (gap < min_gap)
{
result = sum;
min_gap = gap;
}
if (sum < target) ++b;
else --c;
}
}
return result;
}
該算法的改進就是在 if (sum < target) ++b;
else --c;
處，處理掉對重復元素的檢測， 改為b = upper_bound(b,c,*b); c= prev(lower_bound(b,c,*c)); 這樣處理後算法，只有常數級別的優化
4.
4Sum
Total Accepted: 18939 Total Submissions: 88978My SubmissionsGiven 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:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- 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)
解： 初始的方法，三個for循環，找第四個數，即使用二分法，也需要n^3*log(n),超時
參考答案後AC的，思路是先緩存兩個數的和到集合中，這樣空間增大來縮短時間
class Solution {
public:
vector > fourSum(vector &num, int target) {
//注意兩個> >之間有個空格，否則成了>>右移了
if (num.size() < 4) return vector >();
//依然考慮少於4的情況
sort(num.begin(),num.end());
// 排序 map > > cache; // int 對應一個 vector ，vector裡放的幾個pair
for (int a = 0; a < num.size(); ++a)
for (int b = a + 1; b < num.size(); ++b)
cache[num[a] + num[b]].push_back(pair(a,b));
//把和當做key，對應其兩個值，
//注意這裡，和為某個值可能有好多對，而map是一對一，這裡的push_back可不是map的操作，而是一個和值，對應一個vector,vector的push_back操作，另外vector裡存的是元素是pair,每個pair有兩個數。同理下面那個cache[key]的size也是vector
set > result;
//set本身有去重效果，其當內有重復key時，自動忽略後來的
for (int c = 2; c < num.size(); ++c)
//這種int c，也有用的size_t c ;來定義 for (int d = c + 1; d < num.size(); ++d)
//size_t 類型定義在cstddef頭文件中， {
//該文件是C標准庫的頭文件stddef.h的C++版。它是一個與機器相關 int key = target - num[c] - num[d];
//的unsigned類型，其大小足以保證存儲內存中對象的大小。 if (cache.find(key) != cache.end())
//在想用這個，是不是怕數組大小大出int表示范圍。 {
for (int k = 0; k < cache[key].size(); ++k)
//一個和可能有多個對
{
if (c <= cache[key][k].second) continue;
//這裡是防止重復查找，兩個數依次向前，查兩個數的和可以查
result.insert(vector {num[cache[key][k].first],
//其後面的，也可以其前面的，但是不用都查，比如
num[cache[key][k].second],num[c],num[d]});
//一直查，前面的，後面的隨cd增大也會查到
}
}
}
return vector >(result.begin(),result.end());
}
};
