1. 方法一 哈希表
算法思想：利用类似于T1-twoSum哈希表的方法求取三元组。通过第一重循环固定第一个元素a，从而在内部求取两个数b,c，使得b+c = target，内部就转换成了T1两数之和的问题。时间复杂度为T(n)=O(n^2)
该方法值得注意的几个点：
- 由于题目要求类似于[a,b,c]或者[b,a,c]的情况不得重复出现，同时要满足a<b<c，因此在遍历之前首先要对数组进行排序，时间复杂度位O(n^2)。
- 在第一层循环时，如果当前的元素nums[i]在此前遍历时出现过且再次出现时，只需要跳过即可，因为对于第一个元素位nums[i]的情况在此前的循环中必然已经处理过，不需要在考虑。
- 另外，在twoSum函数里在确定对于三元组第三个元素时，也不考虑之前已经出现过且满足和为target的相同元素c，直接跳过。因为是数组已经排过序，所以如果此元素满足要求，在此之前必然被写入到ans的最后一个位置，因此只需验证当前元素是否等于ans最后一个元素即可知道是否已经出现过该元素；此处为什么不使用同上2的做法
nums[i]==nums[i]相同元素即掠过，这是因为可能出现target=2，元素序列为1,1,1…的这类情况，第一个1显然不满足和之前的数加和等于target的要求，但对于第二个1，因此第二个1不能被直接跳过，这类情况简单概括为：“三元组的第2和第三个元素有相同的情况”，所以只能在同一元素第三次出现时跳过，而不是像第一个元素一样，出现第二次就跳过。因此要采用另一种思路：当合格的三元组第三个位置的元素第二次出现时即略过，此处的合格即是这一数字被加入到了ans，如此一来思路就直接很多。 - 注意ans的初始化：
int **ans = (int**)malloc(sizeof(int*) * basicSize);
i. ans是一个二级指针，亦即是一级指针数组的首地址。因为输出必然是多个三元组，每一个三元组是一个数组a【意即 int[]或者int*】，而多个三元组构成的输出即是数组的数组ans【意即int*[] （这里是指针数组，数组的每一个元素都是一个int的指针，每一个指针都指向一个三元组，指针名即是三元组的数组名）或int**】。由此第一个三元组即可表示为ans或者ans[0]，第二个三元组即表示为*(ans+1)或者 ans[1]，ans[*returnSize] = (int*)malloc(sizeof(int)*2);因此对于这句由于此时ans[returnSize]=NULL，因此需要为指针数组ans第returnSize个指针申请一个三元组空间，此处也可写为*(ans+*returnSize)= (int*)malloc(sizeof(int)*2);。
ii. 这里使用basicSize是因为我们起初不知道输出究竟有几个三元组，而如果直接申请一个非常大的空间对于内存是巨大的负担，为了解决这个问题，采用类似于vector类似的申请空间的办法：有一个初始的capacity，此处即是basicSize，当当前的空间被填满即*returnSize==basicSize，重新分配2倍空间并将元素迁移到新的空间中【当然此处是通过realloc函数在重分配空间的同时让计算机自动迁移，不需要显示地写出代码，这种内存的分配方法根据算法分析里面的amortized analysis即平摊分析（假设增加新元素消耗的时间和元素迁移的时间都是1），也是O(n)的时间复杂度（同dynamic table)】。 - 对于函数参数里的
int** returnColumnSizes，这里其实是想存储每一个三元组的元素个数，当然其实每一个都是3，这个地方显得有些鸡肋。但对于此处申请空间的步骤上值得注意，虽然它同ans都是一个二级指针，但申请空间方法是不一样的。要注意*returnColumnSizes = (int*)malloc(sizeof(int) * basicSize)同ans = (int**)malloc(sizeof(int*) * basicSize)的区别，这里之所以这么操作，是因为returnColumnSizes是由外部通过值传递传进来的一个二级指针，因此我们改变returnColumnSizes是没有用的事情，因此为了将信息传递回主函数，只能通过对该二级指针指向的一级指针做文章。每一个三元组对应的size都需要一个对应的int空间来存储，因此若干个三元组则需要一个整数数组int[]或者说int*，因此需要returnColumnSize指向的空间填入一个int的值，因此即有上述写法。通过returnColumnSizes即得到存储三元组size数组的首地址。当然，此处同样因为不知道三元组数量的原因，也需要通过realloc不停地重新分配空间。
C语言实现
struct HashTable{
int _key;
int _val;
UT_hash_handle hh;
};
struct HashTable *hashtable;
struct HashTable *find(int ikey){
struct HashTable *tmp;
HASH_FIND_INT(hashtable, &ikey, tmp);
return tmp;
}
void insert(int ikey, int ival){
struct HashTable *it = find(ikey);
if(it == NULL){
struct HashTable* tmp = malloc(sizeof(struct HashTable));
tmp ->_key = ikey;
tmp ->_val = ival;
HASH_ADD_INT(hashtable, _key, tmp);
}else{
it ->_val = ival;
}
}
int **twoSum(int *nums, int start, int numsSize, int target, int *returnSize){
hashtable = NULL;
int basicSize = 2;
int **ans = NULL;
for(int i = start; i < numsSize; ++i){
if((*returnSize != 0) && nums[i] == ans[(*returnSize)-1][1]){
continue;
}
struct HashTable* it = find(target - nums[i]);
if(it != NULL){
if(*returnSize == 0){
ans = (int**)malloc(sizeof(int*)*basicSize);
}
if(*returnSize == basicSize){
basicSize *= 2;
ans = (int**)realloc(ans, sizeof(int*)*basicSize);
}
ans[*returnSize] = (int*)malloc(sizeof(int)*2);
ans[*returnSize][0] = it ->_key;
ans[*returnSize][1] = nums[i];
++(*returnSize);
}else{
insert(nums[i], i);
}
}
return ans;
}
int Compare(const void *a, const void *b){
int *pa = (int*)a;
int *pb = (int*)b;
return *pa - *pb;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
qsort(nums, numsSize, sizeof(int), Compare);
int **ans = (int**)malloc(sizeof(int*) * basicSize);
int basicSize = 8;
*returnSize = 0;
*returnColumnSizes = (int*)malloc(sizeof(int) * basicSize);
for(int i = 0; i < numsSize-2; ++i){
int curSize = 0;
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
int** curAns = twoSum(nums, i+1, numsSize, -(nums[i]), &curSize);
for(int idx = curSize-1; idx >= 0; --idx){
if(*returnSize == basicSize){
basicSize *= 2;
ans = (int**)realloc(ans, sizeof(int*)*basicSize);
(*returnColumnSizes) = (int*)realloc((*returnColumnSizes),sizeof(int)*basicSize);
}
ans[*returnSize] = (int*)malloc(sizeof(int)*3);
ans[*returnSize][0]=nums[i];
ans[*returnSize][1]=curAns[idx][0];
ans[*returnSize][2]=curAns[idx][1];
(*returnColumnSizes)[*returnSize] = 3;
++(*returnSize);
free(curAns[idx]);
}
if(curAns != NULL){
free(curAns);
}
}
return ans;
}
C++实现
class Solution {
public:
vector<vector<int>> twoSum(vector<int>& nums, int start, int target){
vector<vector<int>> ans;
unordered_map<int, int> hashtable;
int len = nums.size();
for(int i = start; i < len; ++i){
if(ans.size() != 0 && nums[i] == ans[ans.size()-1][1]){
continue;
}
auto it = hashtable.find(target - nums[i]);
if(it != hashtable.end()){
ans.push_back({it->first, nums[i]});
}else{
hashtable[nums[i]] = i;
}
}
return ans;
}
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
int len = nums.size();
sort(nums.begin(), nums.end());
for(int i = 0; i < len-2; ++i){
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
vector<vector<int>> curAns = twoSum(nums, i+1, -(nums[i]));
for(int j = curAns.size()-1; j >= 0; --j){
ans.push_back({nums[i], curAns[j][0], curAns[j][1]});
}
}
return ans;
}
};
------------------------------------------方法二 待续------------------------------------------
欢迎指正
|