博客

索引：

[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)


Github:

https://github.com/illuz/leetcode

001.Two_Sum (Medium)

链接

：

题目：

https://oj.leetcode.com/problems/two-sum/


代码(github)：

https://github.com/illuz/leetcode

题意

：

一个数组中两个位置上的数的和恰为 target，求这两个位置。

分析

：

暴力找过去复杂度是 O(n^2)，会 TLE。

1. 可以先排序再用双指针向中间夹逼，复杂度 O(nlogn)。
2. 可以用 Map 记录出现的数，只要判断有没有和当前的数凑成 target 的数，再找出来就行，复杂度 O(nlogn) 而不是 O(n) ，因为 Map 也要复杂度的。
3. 在 2 中的 Map 复杂度可以用数组来弥补，时间复杂度是 O(n) ，不过空间复杂度是 O(MAXN)。

代码

：

方法一：双指针

class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
            int sz = numbers.size();
            int left = 0, right = sz - 1, sum = 0;

            vector<int> sorted (numbers);
            std::sort(sorted.begin(), sorted.end());

            vector<int> index;
            while (left < right) {
                sum = sorted[left] + sorted[right];
                if (sum == target) {
                    // find the answer
                    for (int i = 0; i < sz; i++) {
                        if (numbers[i] == sorted[left])
                            index.push_back(i + 1);
                        else if (numbers[i] == sorted[right])
                            index.push_back(i + 1);
                        if (index.size() == 2)