力扣 三数之和-15

发布于:2024-11-28 ⋅ 阅读:(19) ⋅ 点赞:(0)

三数之和-15

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int temp = 0;
        //定义一个二维vector数组
        vector<vector<int>> ans;
        int n = nums.size();
        //对nums数组进行排序
        sort(nums.begin(), nums.end());
        //固定索引为k的元素,利用双指针去找另外两个元素与这个固定元素相加之和为0
        for (int k = 0; k < n; k++) {//
        //跳过相同元素
            if (k > 0 && nums[k] == nums[k - 1])
                continue;
            //定义双指针,l从k+1开始遍历,r从n-1开始遍历
            int l = k + 1, r = n-1;
            //while循环开始找符合条件的另外两个数
            while (l < r) {
                //题目要求l != r && l != k && r != k
                if (l != r && l != k && r != k) {
                    //如果固定的值小于0,那么另外两个值的加和应该为fabs(nums[k])
                    if (nums[k] < 0) {
                        //找到两数加和等于fabs(nums[k]),说明已经找到另外两个数了
                        if (nums[l] + nums[r] == fabs(nums[k])) {
                            //将固定的数和另外找到的两个存入二维数组中
                            ans.push_back({nums[k], nums[l], nums[r]});
                            //利用两个while循环跳过相同元素
                            while (l < r && nums[l] == nums[l + 1])
                                l++;
                            while (l < r && nums[r] == nums[r - 1])
                                r--;
                            //移动指针
                            l++;
                            r--;
                        //如果两数加和大于fabs(nums[k]),缩小右边界
                        } else if (nums[l] + nums[r] > fabs(nums[k]))
                            r--;
                        //如果两数加和小于fabs(nums[k]),缩小左边界
                        else
                            l++;
                    }
                    //如果固定的值大于等于0,那么另外两个值的加和应该为-nums[k],其余同上面相似
                    if (nums[k] >= 0) {
                        if (nums[l] + nums[r] == -nums[k]) {
                            ans.push_back({nums[k], nums[l], nums[r]});
                            while (l < r && nums[l] == nums[l + 1])
                                l++;
                            while (l < r && nums[r] == nums[r - 1])
                                r--;
                            l++;
                            r--;
                        } else if (nums[l] + nums[r] > -nums[k])
                            r--;
                        else
                            l++;
                    }
                }
            }
        }
        return ans;
    }
};

每日问题

什么是C++中的模板特化和偏特化?如何进行模板特化和偏特化?

C++中的模板特化和偏特化

        模板特化和偏特化是C++模板的高级特性,用于为特定类型或参数模式提供专门的实现。

1.模板特化

        模板特化是对模板进行完全具体化,提供针对某些特定类型的特殊实现,而不使用通用模板版本。

如何进行模板特化

        定义一个通过模板。

        使用template<>语法为特定类型定义专门的实现。

语法
template<typename T>
class MyClass{
  //通用模板  
};
template<>//模板特化
class MyClass<int>{
    //针对int类型的实现
}
示例
#include<iostream>
using namespace std;
//通用模板
template<typename T>
class MyClass{
public:
    void display(){
        cout<<"General template" <<endl;    
    }
};
//模板特化:针对int类型
template<>
class MyClass<int>{
public:
    void display(){
        cout<<"Specialized for int"<<endl;    
    }
};
int main(){
    MyClass<double>obj1;
    obj1.display();//输出:General template
    
    MyClass<int>obj2;
    obj2.diplay();//输出:Specialized for int
    
    return 0;
}
应用场景

        为特定类型提供优化的实现

        针对某些类型实现特殊的逻辑

2.模板偏特化

        模板偏特化是部分具体化模板的实现。它允许固定某些模板参数的值或模式,而其他参数仍保持通用性。

如何进行模板偏特化

        定义一个通用模板。

        使用部分模板参数固定,定义偏特化的实现。

语法
template<typename T1,typename T2>
class MyClass{
    //通用模板    
};
template<typename T>
class MyClass<T,int>{
    //偏特化版本,第二个参数固定为int
}
示例
#include<iostream>
using namespace std;
//通用模板
template <typename T1,typename T2>
class MyClass{
public:
    void display(){
        cout<<"General template"<<endl;   
    }
};
//偏特化版本:第二个参数固定为int
template <typename T>
class MyClass <T,int>{
public:
    void display(){
        cout<<"Partial specialization where T2 = int" << endl;   
    }
};

int main(){
    MyClass<double,char>obj1;
    obj1.display();//输出:General template
    
    MyClass<double,int>obj1;
    obj2.display();//输出:Partial specialization where T2 = int
    return 0;                
}

应用场景

        当部分参数固定时,使用特化版本以实现优化不同逻辑。

        为一组特定类型的组合提供定制的行为

3.特化与偏特化的区别

4.偏特化的限制

        偏特化无法直接用于函数模板,只能用于类模板

        可以通过函数重载或SFINAE(模板的替代失败非错误)来模拟函数模板偏特化。

函数模板重载实例
#include<iostream>
using namespace std;
template <typename T>
通用函数模板
void func(T val){
    cout<<"General template:"<<val<<endl;
}
//函数模板重载:针对 int 类型
void func(int val){
    cout<<"Specialized for int:"<<val<<endl;
}
int main(){
    func(3.14);//输出:General template:3.14
    func(42);//输出:Specialized for int:42
    
    return 0;
}

总结

1.模板特化:

        完全具体化,为特定类型实现特殊版本。

        使用template<>语法。

2.模板偏特化:

        部分具体化,处理一组参数模式。

        使用部分固定参数定义版本。

3.函数模板没有偏特化 ,可以使用重载或SFINAE间接实现类似效果。特化和偏特化使模板更灵活,可用于优化、处理特殊类型或参数模式的需求。