LeetCode.两数之和&三数之和&最接近的三数之和&四数之和-白红宇

LeetCode.两数之和&三数之和&最接近的三数之和&四数之和

阅读量：792 次

发布时间：2023-01-31

本文共 3484 字，大约阅读时间需要 11 分钟。

LeetCode1.两数之和

做了三数之和就会想为什么两数之和不能用双指针，同样是没有排序！

而且map法每次count的时间复杂度为O(logN)，遍历一遍的时间复杂度为O(NlogN)

双指针排序+搜索的复杂度为O(NlogN+N)，差不多的

注意两数之和这题是要求下标，排过序之后下标就和原来的不一样了……

再弄个map解决映射关系？？个人觉得没必要了

一开始当然是暴力模拟去求解，由于测试样例给的很小，不存在大数情况，可以通过；

当然PAT有类似的题目，PAT中测试点数字很大，暴力方法很显然行不通；

其实这道题使用哈希表来求解，可以将时间复杂度降低一个数量级；

复习一下STLmap的使用方法：

暴力解法：

class Solution {public:    vector
   
     twoSum(vector
    
     & nums, int target) {        vector
     
       v;        for(int i=0;i

哈希表优化解法：

class Solution {public:    vector
   
     twoSum(vector
    
     & nums, int target) {        unordered_map
     
       m;//key是值，value是下标        vector
      
        ans;        for(int i=0;i
       
        0){                ans.push_back(m[target-nums[i]]);                ans.push_back(i);                break;            }            m[nums[i]] = i;        }        return ans;    }};

LeetCode3.三数之和

基本思路：

这算是一道经典的双指针的题目，在排序数组中寻找何为某一个数的题目，下意识的考虑双指针，而不仅仅是二分！

在这道题目没有排序的条件，但是思考很久，没有比排序后再用双指针的解法时间复杂度来的低！

这里剪枝的关键之处：会出现重复的answer，所以要进行剪枝

不同的剪枝的方法，会导致超时：

剪枝的最简单的方法，自然是在ans里find是否有重复的，但是find的复杂度至少为O(N)，所以会超时！

class Solution {public:    vector
   
    
     > threeSum(vector
     
      & nums) {        vector
      
       
        > ans;        if(nums.size()<3)            return ans;        sort(nums.begin(),nums.end());        if(nums[0]>0)            return ans;        for(int i = 0; i
        
         0) break; int left = i+1; int right = nums.size()-1; while(left

temp; temp.push_back(nums[i]); temp.push_back(nums[left]); temp.push_back(nums[right]); // 直接find的去重方法会超时，看来要使用其他方法进行剪枝 if(find(ans.begin(),ans.end(),temp)==ans.end()){ ans.push_back(temp); } left++; right--; }else if(nums[left]+nums[right] < (0-nums[i])){ left++; }else{ right--; } } } return ans; }};

正确剪枝解法：

class Solution {public:    vector
   
    
     > threeSum(vector
     
      & nums) {        vector
      
       
        > ans;        if(nums.size()<3)            return ans;        sort(nums.begin(),nums.end());        if(nums[0]>0)            return ans;         int i = 0;        while(i
        
         0) break; // 使用双指针法进行查找 int left = i+1, right = nums.size()-1; while(left< right){ // 转换为long long避免加法过程中溢出 long long y = static_cast
         
          (nums[i]); long long x = static_cast
          
           (nums[left]); long long z = static_cast
           
            (nums[right]); if(x + y >0-z) right--; else if(x + y <0-z) left++; else{ ans.push_back({nums[i], nums[left], nums[right]}); // 相同的left和right不应该再次出现，因此跳过 while(left

LeetCode16.最接近的三数之和

同样也是双指针，思路和前面的三数之和完全一样，只是多了一个取绝对值比较的过程

class Solution {public:    int threeSumClosest(vector
   
    & nums, int target) {        sort(nums.begin(),nums.end());        int closeNum = nums[0] + nums[1] + nums[2];        for(int i = 0; i
    
     target){                    right--;                }else if(threeSum

LeetCode18.四数之和

思路也还是双指针法，就是比之前的三数之和基础上添加了一重循环的比较过程

class Solution {public:    vector
   
    
     > fourSum(vector
     
      & nums, int target) {        sort(nums.begin(),nums.end());        vector
      
       
        > result;        int size=nums.size();        for(int a=0;a
        
         0&&nums[a]==nums[a-1])continue; for(int b=a+1;b
         
          a+1&&nums[b]==nums[b-1])continue; int i=b+1,j=size-1; while(i
          
           target) while(i

{nums[a],nums[b],nums[i],nums[j]}); while(i

转载地址：http://zmgyk.baihongyu.com/