Time Cost

24min25s. My first solution is nlogn which is over time limit. I always over-complicate the problem ;_;

Code

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

        // for (int i=0; i<size; i++) {
        //     int tr = binarysearch(numbers, target-numbers[i], i+1, size-1);
        //     cout << "try " << numbers[i] << ", result=" << tr << endl;
        //     if (tr != -1) return {i+1, tr+1};
        // }
        // return {0, 0};

        int left = 0, right = size-1;
        while (left < right) {
            if (numbers[left] + numbers[right] > target) {
                right--;
            }else if (numbers[left] + numbers[right] < target) {
                left++;
            }else {
                return {left+1, right+1};
            }
        }
        return {0,0};
    }

    // fixed left, find right matched
    // int binarysearch(vector<int> numbers, int target, int base, int ceil) {
    //     int left = base, right = ceil, mid = (left + right) / 2;
    //     while (left <= right) {
    //         if (numbers[mid] == target) {
    //             return mid;
    //         }else if (numbers[mid] < target) {
    //             left = mid + 1;
    //             mid = (left + right) / 2;
    //         }else {
    //             right = mid - 1;
    //             mid = (left + right) / 2;
    //         }
    //     }
    //     return -1;
    // }

};