57-三数之和
思路
参考资料
首先升序排序数组
然后定义下标变量 k , i , j 。如果简单的遍历，那么跟是否有序没有关系，其时间复杂度将达到O(n^3)。
但是，如果当前选择了a、b、c三个数，如果其和小于目标target，那么需要将其中一个数用更大的数替换；反之亦然。但究竟替换三个数中的哪个数？可以先固定一个数（k），当前值小于target时，可以让 i 增加；否则，j 减小。
code
class Solution {
public:
/**
* @param numbers : Give an array numbers of n integer
* @return : Find all unique triplets in the array which gives the sum of zero.
*/
vector<vector<int> > threeSum(vector<int> &nums) {
// write your code here
int size = nums.size(), target = 0;
if(size < 3) {
return vector<vector<int> >();
}
vector<vector<int> > result;
int i = 0, j = 0, k = 0;
sort(nums.begin(), nums.end());
for(k=0; k<size; k++) {
if(k>0 && nums[k]==nums[k-1]) {
continue;
}
for(i=k+1, j=size-1; i<j;) {
if(i>k+1 && nums[i]==nums[i-1]) {
i++;
continue;
}
if(j<size-1 && nums[j]==nums[j+1]) {
j--;
continue;
}
int sum = nums[i] + nums[j] + nums[k];
if(target == sum) {
vector<int> temp;
temp.push_back(nums[k]);
temp.push_back(nums[i]);
temp.push_back(nums[j]);
result.push_back(temp);
i++;
j--;
}
else if(target < sum) {
j--;
}
else {
i++;
}
}
}
return result;
}
};