题目描述

给出一个升序排列好的整数数组，找出2个数，它们的和等于目标数。返回这两个数的下标（从1开始），其中第1个下标比第2个下标小。

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2假定只有一个正确答案。

我的解法/简便解法——双指针

题目说了数组是排序的，这样难度就降低了。由于数组是升序排列，所以两个数之和sum为目标值target，则肯定是小的数在前，大的数在后，这样明显是双指针的问题。
n的复杂度。
结果：beat 39.53%

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0,j = numbers.length - 1;
        int[] res = new int[2];
        while(i < j){
            int now = numbers[i] + numbers[j];
            if(now > target)
                j--;
            else if(now < target)
                i++;
            else{
                res[0] = i + 1;
                res[1] = j + 1;
                return res;
            }
            
        }
        return res;
    }
}

其他解法——哈希

利用字典，同leetcode第1题
复杂度为n

def twoSum2(self, numbers, target):
    dic = {}
    for i, num in enumerate(numbers):
        if target-num in dic:
            return [dic[target-num]+1, i+1]
        dic[num] = i

其他解法——二分查找

固定一个数字，然后对另一个数字进行二分查找
时间复杂度O(n)

def twoSum(self, numbers, target):
    investigatedSoFar = []
    for i in range(len(numbers)):
        if not numbers[i] in investigatedSoFar:
            investigatedSoFar.append(numbers[i])
            l, r = i + 1, len(numbers) - 1
            tmp = target - numbers[i]
            while l <= r:
                mid = l + (r-l) // 2
                if numbers[mid] == tmp:
                    return([i + 1, mid + 1])
                elif numbers[mid] < tmp:
                    l = mid + 1
                else:
                    r = mid - 1