leetcode 15. 3Sum 双指针

题目链接

给n个数, 找出三个数相加结果为0的所有的组, 不可重复。

用双指针的思想,O(n^2)暴力的找, 注意判重复。

 class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int sz = nums.size();
vector <vector<int> > ans;
vector <int> tmp;
sort(nums.begin(), nums.end());
for(int i = ; i<sz; i++) {
if(i> && nums[i] == nums[i-])
continue;
int l = i+, r = sz-;
while(l<r) {
int sum = nums[i]+nums[l]+nums[r];
if(sum < ) {
l++;
} else if (sum>) {
r--;
} else {
tmp.push_back(nums[i]);
tmp.push_back(nums[l++]);
tmp.push_back(nums[r--]);
sort(tmp.begin(), tmp.end());
ans.push_back(tmp);
tmp.clear();
while(l<r&&nums[l-]==nums[l])
l++;
while(r>l&&nums[r] == nums[r+])
r--;
}
}
}
return ans;
}
};
上一篇:Babelfish(二分查找,字符串的处理略有难度,用sscanf输入)


下一篇:android音乐播放器开发 SweetMusicPlayer 智能负载直插式歌词