基础数学（二）两数之和三数之和

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

两数之和_牛客题霸_牛客网

给出一个整型数组 numbers 和一个目标值 target请在数组中找出两个加起来等于目标值的数的下标返回的下标按升序排列。

注返回的数组下标从1开始算起保证target一定可以由数组里面2个数字相加得到

数据范围2≤len(numbers)≤1052≤len(numbers)≤105−10≤numbersi≤109−10≤numbersi≤1090≤target≤1090≤target≤109

要求空间复杂度 O(n)O(n)时间复杂度 O(nlogn)O(nlogn)

【解法一】枚举遍历无法通过


class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        vector<int> res;
        int n = numbers.size();
        for(int i = 0; i < n; i++)
        {
            for(int j = i+1; j < n; j++)
            {
                if(numbers[i]+numbers[j] == target)
                {
                    res.push_back(i+1);
                    res.push_back(j+1);
                    return res;
                }
            }
        }
        return res;
    }
};

【解法二】哈希存储

这道题让我对哈希表又有了新的认知之前每次都是用hash来进行一个数出现的次数于是会写出这样的 mp[arr[i]]++ ++表示这个数出现的次数加一然而这道题把数与其在number中所对应的下标对应着存入map中。然后在后续遍历中如果target-number[i]在map中存在可以直接返回我所需要的下标值。

时间复杂度O(N) 只需遍历一次数组每次在哈希表中查找的时间复杂度为O(1)

空间复杂度为O(N) 创建map

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        vector<int> res;
        map<int, int> mp;
        int n = numbers.size();
        for(int i = 0; i < n; i++)
        {
            int temp = target - numbers[i];
            if(mp.find(temp) == mp.end())
                mp[numbers[i]] = i;
            else{
                res.push_back(mp[temp]+1);
                res.push_back(i+1);
                break;
            }
        }
        return res;
    }
};

三数之和_牛客题霸_牛客网

给出一个有n个元素的数组SS中是否有元素a,b,c满足a+b+c=0找出数组S中所有满足条件的三元组。

数据范围0≤n≤10000≤n≤1000数组中各个元素值满足 ∣val∣≤100∣val∣≤100

空间复杂度O(n2)O(n2)时间复杂度 O(n2)O(n2)

注意

三元组a、b、c中的元素必须按非降序排列。即a≤b≤c
解集中不能包含重复的三元组。

将三数求和转化为二数求和来达到解题的目的使用set接口进行去重。

class Solution {
public:
    vector<vector<int>> TwoSum(vector<int> num, int target, int begin)
    {
        int n = num.size();
        vector<vector<int>> res;    // 用来返回结果数组
        for(int i = begin; i < n; i++)
        {
            int _target = target-num[i];    // 将二数求和转化为找一个数
            if(find(num.begin()+i+1,num.end(),_target) != num.end())
            {
                // 利用#include<algorithm> 中find接口来进行查找
                // 找不到就返回num的end()
                vector<int> temp;
                temp.push_back(num[i]);   //如果找到了就把第二个数与第三个数都放入temp中      
                temp.push_back(_target);    
                res.push_back(temp);      //完成一次结果并放入res中,继续后续其他结果的查找
            }
        }
        return res;
    }
    vector<vector<int> > threeSum(vector<int> &num) {
        set<vector<int>> res;   // 用来去重的set容器
        vector<vector<int>> Res;    // 用来返回结果
        int n = num.size();
        if(n<3)return Res;  // 元素个数小于三个返回空
        sort(num.begin(), num.end());   // 进行一次排序整理
        for(int i = 0; i < n; i++)
        {
            int target = 0-num[i];      // 把三数之和转化为俩数之和
            vector<vector<int>> temp = TwoSum(num, target, i+1);    // 多传一个下标参数 防止重复
            if(!temp.empty())
            {
                for(auto e : temp)
                {
                    e.insert(e.begin(), num[i]); // 在每组返回的数组最前方插入第一个数
                    res.insert(res.end(), e);   // 将三个数的数组放入到set容器中进行去重
                }
            }
        }
        for(auto e : res)
            Res.push_back(e);   // 将set转移至Res中。
        return Res;
    }
};