lintcode/2-sum_2(AC).cpp at master · siXence/lintcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// O(n * log(n)) solution with O(n) space
#include <algorithm>
using namespace std;

struct Term {
    int val;
    int i;
};

bool comp(const Term &x, const Term &y)
{
	return x.val < y.val;
}

class Solution {
public:
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1+1, index2+1] (index1 < index2)
     */
    vector<int> twoSum(vector<int> &nums, int target) {
        vector<int> &a = nums;
        int n = a.size();
        vector<Term> v(n);

        int i, j;
        for (i = 0; i < n; ++i) {
            v[i].val = a[i];
            v[i].i = i + 1;
        }
        sort(v.begin(), v.end(), comp);

        vector<int> ans(2);
        i = 0;
        j = n - 1;
        while (i < j) {
            if (v[i].val + v[j].val < target) {
                ++i;
            } else if (v[i].val + v[j].val > target) {
                --j;
            } else {
                ans[0] = v[i].i;
                ans[1] = v[j].i;
                if (ans[0] > ans[1]) {
                    swap(ans[0], ans[1]);
                }
                break;
            }
        }
        return ans;
    }
};