点击刷新
给一个数组，球里面所有满足 a+b+c = 0的元素
T_T开始想的是hash，然后查0-a-b这个。
但是发现不好处理重复元素的问题。
T_T，那就这样。。。排序。。。然后二分
先枚举a
for(int i = 0 ; i < cap-2 ; i++)
这样也会有重复的问题，所以下个i不应该是i＋＋而且，刚好大于num[i]的那个位置
同理j也是
然后再用二分查找0-a-b这个数是否存在。
当然为了保证不重复，我们另a <= b <= c ,所以只查找后面的元素
class Solution {
public:
int upper(int start , int end , vector<int> &num , int target){
int l = start;
int r = end - 1;
while(l <= r){
int mid = (l + r) / 2;
if(num[mid] <= target) l = mid + 1;
else r = mid -1;
}
return l;
}
bool bsearch(int start , int end , vector<int>&num , int target){
int l = start;
int r = end - 1;
while(l <= r){
int mid = (l + r) / 2;
if(num[mid] == target) return true;
else if(num[mid] > target) r = mid - 1;
else l = mid + 1;
}
return false;
}
vector<vector<int> > threeSum(vector<int> &num) {
// Note: The Solution object is instantiated only once and is reused by each test case.
vector<vector<int> >ans;
if (num.size() < 3) return ans;
sort(num.begin() , num.end());
int cap = num.size();
for(int i = 0 ; i < cap - 2 ; i = upper(i , cap-2 , num , num[i])){
for(int j = i + 1 ; j < cap - 1 ; j =upper(j , cap-1 , num , num[j])){
if(bsearch(j + 1, cap , num , 0 - num[i] - num[j])){
vector<int> tmp;
tmp.push_back(num[i]);tmp.push_back(num[j]);tmp.push_back(0 - num[i] - num[j]);
// cout << num[i] << " " << num[j] << " " << (0 - num[i] - num[j]) << endl;
ans.push_back(tmp);
}
}
}
return ans;
}
};
class Solution { public: int up(const vector<int>& num, int left) { int l = left; int r = num.size() - 1; int key = num[left]; while(l <= r) { int mid = l + (r - l) / 2; if (num[mid] > key) r = mid - 1; else l = mid + 1; } return l; } bool bs(const vector<int>& num, int left, int target) { int l = left; int r = num.size() - 1; while(l <= r) { int mid = l + (r - l) / 2; if (num[mid] == target) return true; if (num[mid] < target) l = mid + 1; else r = mid - 1; } return false; } vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int> > ans; if (num.size() < 3) return ans; sort(num.begin(), num.end()); for (int i = 0; i < num.size() - 2; i = up(num, i)) { for (int j = i + 1; j < num.size() - 1; j = up(num, j)) { bool find = bs(num, j + 1, 0 - num[i] - num[j]); if (find) { vector<int> tmp; tmp.push_back(num[i]);tmp.push_back(num[j]);tmp.push_back(0 - num[i] - num[j]); ans.push_back(tmp); } } } return ans; } };
© 著作权归作者所有
举报
相关热门文章
发表评论
0/200
