两数之和 II - 输入有序数组 - 双指针 O(N) 时间复杂度

来源 https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

思路

仅仅是遍历数组，找到数组中和为target的两个数；这个是利用了二数之和的解法，属于暴力破解了， 针对于无序数组；没有利用到本题的有序数组的特性；

my ugly code

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

func twoSum(numbers []int, target int) []int {
    var res []int
	length := len(numbers)

	for i := 0; i < length-1; i++ {
		for j := i + 1; j < length; j++ {
			sum := numbers[i] + numbers[j]
			if sum == target {
				res = append(res, i+1)
				res = append(res, j+1)
			}
		}
	}

	return res
}

明显上述代码效率就不高， 甚至会达到O(n^2)的复杂度；

对于有序的数组， 我会想到二分查找；

​ 在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。

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

func twoSum(numbers []int, target int) []int {
    for i := 0; i < len(numbers); i++ {
        low, high := i + 1, len(numbers) - 1
        for low <= high {
            mid := (high - low) / 2 + low
            if numbers[mid] == target - numbers[i] {
                return []int{i + 1, mid + 1}
            } else if numbers[mid] > target - numbers[i] {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
    }
    return []int{-1, -1}
}

复杂度分析

​ 时间复杂度：O(nlogn)，其中 n 是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是 O(n)，寻找第二个数使用二分查找，时间复杂度是 O(logn)，因此总时间复杂度是 O(nlogn)。

​ 空间复杂度：O(1)。

高手思路赏析

解题思路：

使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

  • 如果两个指针指向元素的和 sum == target，那么得到要求的结果；

  • 如果 sum > target，移动较大的元素，使 sum 变小一些；

  • 如果 sum < target，移动较小的元素，使 sum 变大一些。

数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。

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

// from  CyC2018
public int[] twoSum(int[] numbers, int target) {
    if (numbers == null) return null;
    int i = 0, j = numbers.length - 1;
    while (i < j) {
        int sum = numbers[i] + numbers[j];
        if (sum == target) {
            return new int[]{i + 1, j + 1};
        } else if (sum < target) {
            i++;
        } else {
            j--;
        }
    }
    return null;
}