Leetcode1:Two Sum-蒲公英云

Leetcode1:Two Sum

心已赠人 2022-08-20 07:24 268阅读 0赞

原题连接：传送门

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

题目大意：

给一个数组和一个特定的值，返回数组中两个数的下标，使得这两个数的和等于给定的数，还要求给出的结果按顺序排放，如：

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

这里我们对数组中的每个数都要保留两个信息，一个是数本身的值，一个是数的下标。因此我们可以定义一个结构体：

struct Node
{
    int val;
    int idx;
};

用val来存储数组中的数值，用idx来存储数的下标。

这是一个典型的双指针问题，将数组升序排序后，从左右两边向中间移动，检查两个位置上数的和，如果和等于给定的值target，说明找到了这对数，把下标保存在vector中接口；如果和大于target，说明有指针位置的数较大，将右侧游标向左移动，左侧游标不动；如果和小于target，说明左侧游标位置的数较小，将左侧游标右移，右侧游标不动，直到找到合适的数对。

可是传过来的参数不是升序排列的，需要我们进行排序。C++中有一个函数sort，下面介绍下C++库中的sort函数。

1.定义：定义在头文件中；

2.函数原型：

template
void sort( RandomAccessIterator first, RandomAccessIterator last );
template
void sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

即sort有两个重载函数，一个需要两个参数：first和last；另一个需要三个参数，first、last和自定义比较函数comp。

sort函数对在[first,last)区间内的元素按照升序排列。函数对相同元素不一定保留原来的次序，同时，第一个函数使用<操作符进行比较，第二个函数使用comp进行比较。

3.参数：

first、last：要比较元素的范围，是一个迭代器；
comp：比较函数，如果第一个参数小于第二个参数返回true。自定义的函数必须满足如下形式：
bool cmp(const Type1 &a, const Type2 &b);

4.返回值：none

5.时间复杂度：
O(N·log(N))

6.例子：

#include <algorithm>
#include <functional>
#include <array>
#include <iostream>
int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    std::sort(s.begin(), s.end());
    for (int a : s) {
        std::cout << a << " ";
    } 
    std::cout << '\n';
    std::sort(s.begin(), s.end(), std::greater<int>());
    for (int a : s) {
        std::cout << a << " ";
    } 
    std::cout << '\n';
}

结果：

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

因此，我们需要给出自己的comp函数来比较Node：

bool cmp(Node a,Node b)
{
    return a.val<b.val;
}

只比较val值即可。

然后，就可以按照上面的描述写代码了：

struct Node
{
    int val;
    int idx;
};
bool cmp(Node a,Node b)
{
    return a.val<b.val;
}
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret(2);
        vector<Node> nodes;
        for(int i=0;i<nums.size();i++)
        {
            Node node;
            node.val=nums[i];
            node.idx=i;
            nodes.push_back(node);
        }
        sort(nodes.begin(),nodes.end(),cmp);
        for(int i=0,j=nodes.size()-1;i!=j;)
        {
            int sum=nodes[i].val+nodes[j].val;
            if(sum==target)
            {
                ret[0]=nodes[i].idx<nodes[j].idx?nodes[i].idx:nodes[j].idx;
                ret[1]=nodes[i].idx+nodes[j].idx-ret[0];
                break;
            }
            else if(sum<target)
                i++;
            else
                j--;
        }
        return ret;
    }
};