Leetcode1:Two Sum

原题连接：传送门

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<int>中接口；如果和大于target，说明有指针位置的数较大，将右侧游标向左移动，左侧游标不动；如果和小于target，说明左侧游标位置的数较小，将左侧游标右移，右侧游标不动，直到找到合适的数对。

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

1.定义：定义在<algorithm>头文件中；

2.函数原型：

• template< class RandomAccessIterator >
  void sort( RandomAccessIterator first, RandomAccessIterator last );
  
• template< class RandomAccessIterator, class Compare >
  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++;elsej--;}return ret;} };
从上面的代码中可以看到，如果没有sort一步，处理过程只需将nodes遍历一遍。

总结

以上是生活随笔为你收集整理的Leetcode1:Two Sum的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。