pic

Two Sum 

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

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

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

分析

题目的意思是，给定一个整形数组,找到其中两个元素相加是特定值，返回这两个元素的下标.

     * 对于未排序的数组来说，设置两层for循环遍历是首先可以想到的方法，复杂度为O(N^2)
     * 将未排序的数组排序后再求twosum，可以优化到O(NlogN)复杂度：
     * 新建一个结构体  struct Node {int val; int seq;}；seq用来存储val在原数组的下标
     * 将Node数组排序后，设置两个指针分别指向数组首元素和尾元素，判断两个指针的Node的val和
     * 是否等于target，等于则按照seq从小到大存到返回数组，小于target，那么将首元素指针右移；
     * 大于target，则将尾元素指针左移；循环终止条件是首指针和尾指针相遇。

Code

struct Node {
    int val;
    int seq;
};
bool compare(Node lhs, Node rhs)
{
    return lhs.val < rhs.val;
}
class Solution {
public:
    /* 
     * 对于未排序的数组来说，设置两层for循环遍历是首先可以想到的方法，复杂度为O(N^2)
     * 将未排序的数组排序后再求twosum，可以优化到O(NlogN)复杂度：
     * 新建一个结构体  struct Node {int val; int seq;}；seq用来存储val在原数组的下标
     * 将Node数组排序后，设置两个指针分别指向数组首元素和尾元素，判断两个指针的Node的val和
     * 是否等于target，等于则按照seq从小到大存到返回数组，小于target，那么将首元素指针右移；
     * 大于target，则将尾元素指针左移；循环终止条件是首指针和尾指针相遇。
     * */
    vector<int> twoSum(vector<int> &numbers, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<int> indexs;
        if(numbers.size() < 2)
            return indexs;
        vector<Node> Nodes(numbers.size());
        for(int idx = 0; idx < numbers.size(); idx++)
            Nodes[idx].val = numbers[idx], Nodes[idx].seq = idx + 1;
        // 排序，复杂度O(NlogN)
        std::sort(Nodes.begin(), Nodes.end(), compare);
        int lptr = 0, rptr = Nodes.size() - 1;
        int tempSum = 0;
        while(lptr < rptr)
        {
            tempSum = Nodes[lptr].val + Nodes[rptr].val;
            if( tempSum == target)
            {
                // 返回的两个下标需要从小到大排序
                if(Nodes[lptr].seq < Nodes[rptr].seq)
                    indexs.push_back(Nodes[lptr].seq), indexs.push_back(Nodes[rptr].seq);
                else
                    indexs.push_back(Nodes[rptr].seq), indexs.push_back(Nodes[lptr].seq);
                break;
            }
            else if( tempSum < target)
                lptr++;
            else
                rptr--;
        }
        return indexs;
    }
};

pic