leetcode第1题，两数之和。采用双指针的算法来完成。

0 前言

从这里开始不定期更新leetcode算法题，其中穿插题目解析，主要用于掌握数据结构基础为主。

1两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

1输入：nums = [2,7,11,15], target = 9
2输出：[0,1]
3解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1输入：nums = [3,2,4], target = 6
2输出：[1,2]

示例 3：

1输入：nums = [3,3], target = 6
2输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

2解题思路（双指针）

对这个数组排序，升序排序，并在数组头尾设置双指针

双指针移动，移动的时候计算

1/*L指针向右移动，R指针向左移动，遍历所有
2**a[L] + a[R]是否等于T
3**只会出现三种场景
4**/
5a[L] + a[R] == T		//找到这个等于，算法结束
6a[L] + a[R] < T			//只能移动L指针
7a[L] + a[R] > T			 //只能移动R指针

3解题

 1//最终答案
 2class Solution {
 3public:
 4    vector<int> twoSum(vector<int>& a, int t) {
 5        int n = a.size();
 6        vector<int> idexs;
 7        for(int i = 0; i < n; i++)
 8        {
 9            idexs.push_back(i);
10        }
11
12        //不能直接排序，会丢失下标
13        sort(idexs.begin(), idexs.end(), [a, idexs](int i, int j){
14            return a[idexs[i]] < a[idexs[j]];
15        });
16
17        int l = 0, r = n - 1;
18        vector<int> ret;
19        while(l < r){
20            int sum = a[idexs[l]] + a[idexs[r]];
21            if(sum == t)
22            {
23                ret.push_back(idexs[l]);
24                ret.push_back(idexs[r]);
25                break;
26            }else if(sum < t)
27            {
28                l++;
29            }else if(sum > t)
30            {
31                r--;
32            }
33        }
34        return ret;
35    }
36};