LeetCode

利用模板解决n数之和

nkul · 9月28日 · 2020年 · 25次已读

题目原型

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那n个整数

或者是

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和最接近目标值的那n个整数

且返回返回下标需要去重!!!!注意返回的不是下标!

模板

这类题目除了两数之和可以利用hash表优化外,均要采用两指针方法,将时间复杂度减小一个次方!以三数之和为例:

  • 对数组进行排序
  • 因为是双指针做法,故n数之和先固定n-2个指针,即for循环
  • 每个for循环第一步,去重。if(i && nums[i] == nums[i – 1]) continue;
  • 利用模板句子 while( j + 1 < k && nums[i] + nums[j] + nums[k-1] >= 0) k– ;
    • 在这段代码中,当nums[i] + nums[j] + nums[k-1] < 0时跳出循环,此时有nums[i] + nums[j] + nums[k] >= 0
  • 最后再判断nums[i] + nums[j] + nums[k] == 0

来看三数之和的代码

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> res;

        //1、排序
        sort(nums.begin(),nums.end());

        //固定第一根指针
        for(int i = 0 ; i < nums.size(); i++ ){

            //每个for循环第一步,去重
            if(i && nums[i] == nums[i - 1]) continue;

            //最内层循环双指针,第一根指针是上一层循环的下一位,第二根指针指向尾部,当相遇时退出
            for(int j = i + 1 , k = nums.size()-1; j < k; j++){

                //for循环内,第一步去重
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;

                //固定句式找最接近target且大于等于target的k
                while( j + 1 < k && nums[i] + nums[j] + nums[k-1] >= 0) k-- ;

                //最后判断是否符合,放入返回数组内!
                if(nums[i] + nums[j] + nums[k] == 0){
                    res.push_back({nums[i], nums[j], nums[k]});
                }
            }
        }
        return res;

    }
};

while( j + 1 < k && nums[i] + nums[j] + nums[k-1] >= 0) k– ;

这段代码中,首先就有 k-1 > j(for循环的要求) 即 j+1 < k

第二因为数组是有序的,想要每次逼近target,k–即可

题目



0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!