LeetCode 167: Two Sum II - Input array is sorted

Difficulty: Easy

Tags: Array, Two Pointers, Binary Search

问题描述

给定一个整型数组 numbers，其中元素按升序排列，给定一个 target。

数组中有2数之和正好为 target，找出这2个数的下标 index1 和 index2。

解决方案

用2个指针 i 和 j，一个从前往后找，另一个从后往前找。

利用数组元素升序的特点：

▷ 如果 numbers[i] + numbers[j] > target，那么 index2 肯定比现在的 j 小

▷ 如果 numbers[i] + numbers[j] < target，那么 index1 肯定比现在的 i 大

▷ Time Complexity: O(n)

▷ Space Complexity: O(1)

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 i = 0;
        int j = numbers.size()-1;

        while(i<j)
        {
            if(numbers[i] + numbers[j] == target)
            {
                vector<int> result{i+1, j+1};
                return result;
            }
            else if(numbers[i] + numbers[j] > target)
            {
                j--;
            }
            else
            {
                i++;
            }
        }
    }
};

回到 Conquer Leetcode