leetcode_two_sum_ii

发表于

难度：Medium

遍历数组，然后在当前元素的右侧，寻找另一个值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i = 0; i < numbers.size(); i++)
        {
            int match = target - numbers[i];
            int left = i+1;
            int right = numbers.size()-1;
            while(left <= right)
            {
                int mid = left+(right-left)/2;
                if(numbers[mid] == match)
                    return {i+1,mid+1};
                else if(numbers[mid] < match)
                    left = mid+1;
                else 
                    right = mid-1;
            }
        }
        return {1,1};
    }
};

运行结果：6ms，超过38.57%

TwoPointers做法。一个left_index在最左侧，一个right_index在最右侧。相加之和，小于target，则left_index++,大于target，则right_index–。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0;
        int right = numbers.size()-1;
        while(left < right)
        {
            int val = numbers[left]+numbers[right];
            if(val == target)
            {
                return {left+1,right+1};
            }
            else if(val > target)
            {
                right--;
            }
            else
            {
                left++;
            }
        }
        return {0,0};
    }
};

运行结果：9ms，超过15.26%