最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

快讯：两数之和、三数之和、四数之和（双指针）

来源：博客园

两数之和：1. 两数之和 - 力扣（LeetCode）

思路：单次循环，利用哈希表 :key存储值，val存储索引；

时间复杂度、空间复杂度 均为 ： O(N)


(资料图片)

class Solution {public:    vector twoSum(vector& nums, int target) {        unordered_maphashtable;        for(int i = 0;i < nums.size();++i){            auto it = hashtable.find(target-nums[i]);            if(it != hashtable.end()){                return {it->second,i};            }            hashtable[nums[i]] = i;        }        return {};    }};

三数之和：15. 三数之和 - 力扣（LeetCode）

思路：排序+双指针， 数组进行排序，方便处理

第一层循环 扫描数组，第二层循环，利用双指针，减少时间复杂度；

第一层和第二层的去重操作，利用continue 跳出此次循环，接着下一次循环

时间复杂度：O(N2)；空间复杂度：O(log N)

class Solution {public:    vector> threeSum(vector& nums) {        int n = nums.size();        sort(nums.begin(),nums.end());        vector>res;        for(int i = 0; i < n; ++i){            if(i > 0 && nums[i] == nums[i-1]) continue;            int k = n -1;            int twoSum = -nums[i];            for(int j = i +1;j < n;++j){                if(j>i+1 && nums[j] == nums[j-1]) continue;                while(j < k && nums[j]+nums[k] > twoSum) --k;                if(j == k) break;//随着j的增加，k要减小                if(nums[j] + nums[k] == twoSum) res.push_back({nums[i],nums[j],nums[k]});            }        }        return res;    }};

四数之和：18. 四数之和 - 力扣（LeetCode）

思路：排序+双指针+剪枝， 数组进行排序，方便处理

去重：如若此数等于上次枚举的数字，直接进入下一次循环---采用continue；

剪枝：nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target；四数之和大于target，因排序数组，所以此后的数字和只能是越来越大，因此退出第一重循环---采用break；

此处防止溢出，采用long long型变量；

nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target；说明此数与最大的三个之和小于target，那么跳出本次循环，开启下一次循环---词用continue；

第一层循环，去重+剪枝，固定第一个数字

第二层循环，去重+剪枝，固定第二个数字

第三层循环，双指针+去重，确定剩下的两个数字

左指针m、右指针k，判断其与剩下的两个数字和的大小，大于则 右指针左移，小于 则 左指针右移，相等就压入数组中，并执行右指针左移，左指针右移；同时判断下一次的值是否与此次相同，即去重操作；

时间复杂度：O(N3) ；空间复杂度：O(log N)

class Solution {public:    vector> fourSum(vector& nums, int target) {        int n = nums.size();        if(n < 4) return {};        sort(nums.begin(),nums.end());        vector>res;        for(int i = 0;i < n-3;++i){            if(i > 0 && nums[i] == nums[i-1]) continue;            if((long long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;            if((long long)nums[i]+nums[n-1]+nums[n-2]+nums[n-3] < target) continue;            for(int j = i+1;j < n-2;++j){                if(j > i+1 && nums[j] == nums[j-1]) continue;                if((long long)nums[i]+nums[j]+nums[j+1]+nums[j+2] > target) break;                if((long long)nums[i]+nums[j]+nums[n-1]+nums[n-2] < target) continue;                int twoSum = target - (nums[i] + nums[j]);                int m = j + 1,k = n-1;                while(m < k){                    if(nums[m]+nums[k] > twoSum) --k;                    else if(nums[m]+nums[k] < twoSum) ++m;                    else{                        res.push_back({nums[i],nums[j],nums[m],nums[k]});                        --k;++m;                        while(m < k && nums[m] == nums[m-1]) ++m;                        while(m < k && nums[k] == nums[k+1]) --k;                    }                               }            }        }        return res;    }};

关键词： 时间复杂度 空间复杂度 进入下一