基础数学二两数:和 三数:和

目录

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

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

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

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

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

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

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

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

1.  
    
2.  
   class Solution {
3.  
   public:
4.  
   vector<int> twoSum(vector<int>& numbers, int target) {
5.  
   // write code here
6.  
   vector<int> res;
7.  
   int n = numbers.size();
8.  
   for(int i = 0; i < n; i )
9.  
   {
10.  
    for(int j = i 1; j < n; j )
11.  
    {
12.  
    if(numbers[i] numbers[j] == target)
13.  
    {
14.  
    res.push_back(i 1);
15.  
    res.push_back(j 1);
16.  
    return res;
17.  
    }
18.  
    }
19.  
    }
20.  
    return res;
21.  
    }
22.  
    };

【解法二】哈希存储

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

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

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

1.  
   class Solution {
2.  
   public:
3.  
   vector<int> twoSum(vector<int>& numbers, int target) {
4.  
   // write code here
5.  
   vector<int> res;
6.  
   map<int, int> mp;
7.  
   int n = numbers.size();
8.  
   for(int i = 0; i < n; i )
9.  
   {
10.  
    int temp = target - numbers[i];
11.  
    if(mp.find(temp) == mp.end())
12.  
    mp[numbers[i]] = i;
13.  
    else{
14.  
    res.push_back(mp[temp] 1);
15.  
    res.push_back(i 1);
16.  
    break;
17.  
    }
18.  
    }
19.  
    return res;
20.  
    }
21.  
    };

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

给出一个有n个元素的数组S，S中是否有元素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)

注意：

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

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

1.  
   class Solution {
2.  
   public:
3.  
   vector<vector<int>> TwoSum(vector<int> num, int target, int begin)
4.  
   {
5.  
   int n = num.size();
6.  
   vector<vector<int>> res; // 用来返回结果数组
7.  
   for(int i = begin; i < n; i )
8.  
   {
9.  
   int _target = target-num[i]; // 将二数求和转化为找一个数
10.  
    if(find(num.begin() i 1,num.end(),_target) != num.end())
11.  
    {
12.  
    // 利用#include<algorithm> 中find接口来进行查找
13.  
    // 找不到就返回num的end()
14.  
    vector<int> temp;
15.  
    temp.push_back(num[i]); //如果找到了就把第二个数与第三个数都放入temp中
16.  
    temp.push_back(_target);
17.  
    res.push_back(temp); //完成一次结果并放入res中,继续后续其他结果的查找
18.  
    }
19.  
    }
20.  
    return res;
21.  
    }
22.  
    vector<vector<int> > threeSum(vector<int> &num) {
23.  
    set<vector<int>> res; // 用来去重的set容器
24.  
    vector<vector<int>> Res; // 用来返回结果
25.  
    int n = num.size();
26.  
    if(n<3)return Res; // 元素个数小于三个返回空
27.  
    sort(num.begin(), num.end()); // 进行一次排序整理
28.  
    for(int i = 0; i < n; i )
29.  
    {
30.  
    int target = 0-num[i]; // 把三数之和转化为俩数之和
31.  
    vector<vector<int>> temp = TwoSum(num, target, i 1); // 多传一个下标参数 防止重复
32.  
    if(!temp.empty())
33.  
    {
34.  
    for(auto e : temp)
35.  
    {
36.  
    e.insert(e.begin(), num[i]); // 在每组返回的数组最前方插入第一个数
37.  
    res.insert(res.end(), e); // 将三个数的数组放入到set容器中进行去重
38.  
    }
39.  
    }
40.  
    }
41.  
    for(auto e : res)
42.  
    Res.push_back(e); // 将set转移至Res中。
43.  
    return Res;
44.  
    }
45.  
    };

这篇好文章是转载于：学新通技术网