The problem asks: given an array numbers and a target, find two indices index1 and index2 such that the two numbers at those indices sum to target.

Note that the indices in numbers start from 1, but vector as a built-in array actually has 0-based indexing.

Since I just started doing LeetCode problems, I’m still getting used to it – it’s quite different from the online judges I used before.

In particular, I had never worked with vector before, and now I truly realize how much of a C++ beginner I am.

Here’s a blog post for learning about vectors: http://www.cnblogs.com/charley_yang/archive/2010/12/11/1903040.html

Just treat vector as an array.

Here’s my solution and approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        vector<int> answer(2);
        for(int i = 0; i < numbers.size(); i++) {
            int flag = false;
            for(int j = 0; j < numbers.size(); j++) {
                if(i != j && numbers[i] + numbers[j] == target) {
                    answer[0] = i + 1;
                    answer[1] = j + 1;
                    flag = true;
                    break;
                }
            }
            if(flag == true) break;
        }
        return answer;
    }
};

The approach is straightforward – brute force.

Got AC on the first try, though the runtime was 32ms. This method is $O(n^2)$ – can we do better?

I thought about it: if we sort the vector first in $O(n \log n)$, then for each number, compute the difference with target and binary search for it, the overall complexity would be $O(n \log n)$. That should be faster – though we’d need to handle index preservation.