题目简述

题目链接：https://leetcode.cn/problems/two-sum/

简述：给一个整数序列和一个结果，在序列中找出和为结果的两个整数，返回它们的数组下标。答案存在且唯一。

题解

思路一：枚举

两层循环，第一层循环确定第一个数，第二层循环确定第二个数，看两个数相加是否等于结果。如果成立，则输出两个数的位置，跳出循环。

时间复杂度为O(n^2)，空间复杂度为O(n)。

思路二：维护一个数据结构，降低找第二个数的复杂度

思路一时间复杂度高的原因在于找第二个数的效率太低了，要遍历一遍序列去看是否存在。

• 将序列排序，然后通过二分查找的方式去寻找第二个数是否存在，这样找第二个数的时间复杂度降低到了O(log_2n)，整体算法时间复杂度降低到了O(nlog_2n)。

  如果采用循环方式实现二分查找，空间复杂度就是O(1)的；如果采用递归方式实现二分查找，空间复杂度就是O(log_2n)的，相比于N来说，都是常数级别，所以算法整体空间复杂度还是O(n)。

• 使用map实现有序查找。map对应的数据结构是红黑树，是一种近似于平衡的二叉查找树，里面的数据是有序的。在红黑树上查找、插入、删除的时间复杂度为O(log_2n)，所以算法整体时间复杂度是O(nlog_2n)。本题我采用的是这种方式。

代码

• 使用map实现有序查找，降低找第二个数的复杂度。
• 代码链接：https://gitee.com/sigmapoet/myleetcode/tree/master/1-100/1.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C

typedef vector<int> posQueue;
typedef struct numAttr {
    bool isExisted;
    posQueue pos;
}numAttr;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, numAttr> num;
        vector<int>::iterator it;
        vector<int> answer;
        int curPos = 0;
        for(it = nums.begin(); it != nums.end(); ++ it) {
            if(!num[*it].isExisted) {
                num[*it].isExisted = true;
                num[*it].pos.push_back(curPos);
            }
            else {
                num[*it].pos.push_back(curPos);
            }
            curPos ++;
        }

        int sumA, sumB;
        for(it = nums.begin(); it != nums.end(); ++ it) {
            sumA = *it;
            sumB = target - sumA;
            if(sumA == sumB) {
                if(num[sumA].pos.size() > 1) {
                    answer.push_back(num[sumA].pos[0]);
                    answer.push_back(num[sumA].pos[1]);
                    break;
                }
            }
            else if(num[sumB].isExisted) {
                answer.push_back(num[sumA].pos[0]);
                answer.push_back(num[sumB].pos[0]);
                break;
            }
        }
        return answer;
    }
};