leetcode:3Sum
來源：程序員人生 發布時間：2015-01-09 08:38:46 閱讀次數：2617次
1、 題目
給出1個數組S包括n個整數，找出不重復的3個元素a、b、c使a+b+c=0。
例如給出S = {⑴0 1 2 ⑴ ⑷},
結果是:
(⑴, 0, 1)
(⑴, ⑴, 2)
2、 分析
首先我們看到這個題目會想到Brute-Force(簡單的模式匹配)直接使用3重循環來匹配所有元素組合找出結果。雖然我在每層循環都做了優化來減少1些遍歷，但是依然不能在數量級上減少，所以總是超時。
Brute-Force(簡單的模式匹配)超時期碼：
//超時
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
int len = num.size();
int res;
vector<vector<int>> ans;
if(len<=2) return ans;
for(int i=0;i<len⑵;i++){
for(int j=i+1;j<len⑴;j++){
res = 0-num[i]-num[j];
for(int k=j+1;j<len;j++){
if(num[k] == res){
vector<int> ves;
ves.push_back(num[i]);
ves.push_back(num[j]);
ves.push_back(num[k]);
ans.push_back(ves);
}
}
}
}
return ans;
}
};
所以我們要換個思路，1般情況下對數組的查詢我們為了方便總是希望它是有序的，因此第1步應當要將數組排序，那末接下來我們就將當前的節點作為第1個元素，那末接下來就是尋覓剩下的兩個元素，由于它已是有序的了，所以可使用左右指針法，設置左右指針夾逼，總的時間復雜度為O(n^2+nlogn)=(n^2),空間復雜度是O(n)
但注意為了不重復，對排序后的數組，當我們枚舉第1個數時，如果遇到重復的就直接跳過，這1點其實很重要，我沒有寫的時候1會超時；還有1點當我們找到1個符合的2元組（第2個數和第3個數）時，也分別對第2個數和第3個數去重。可以看出這道題細節處理是不是到位決定了能否通過。
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
int len = num.size();
//中間結果、左指針、右指針
int res,left,right;
vector<vector<int>> ans;
if(len<=2) return ans;
//將數組排序
sort(num.begin(), num.end());
for(int i=0;i<len⑵;i++){
//將重復的疏忽，ps：剛開始沒有關心這1點,總是超時，加上后秒過，汗...
while(i > 0 && i < len - 2 && num[i] == num[i - 1])
++i;
res = -num[i];
left = i+1;
right = len ⑴;
while(left<right){
//尋覓符合元素
if(num[left] + num[right] < res){
left++;
}
else if(num[left] + num[right] > res){
right--;
}
else {
//將結果放入ans
vector<int> ves;
ves.push_back(num[i]);
ves.push_back(num[left]);
ves.push_back(num[right]);
ans.push_back(ves);
//解決重復問題
left++;
while(left < right && num[left] == num[left⑴])
left++;
right--;
while(left < right && num[right] == num[right+1])
right--;
}
}
}
return ans;
}
};
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
