双指针可以解决2-sum问题的数学证明

设存在长度为的升序数列为，设一个目标值为，假设唯一存在一对，即,使得。

要求证明双指针算法可以在存在的时候找到这对值。

双指针算法的Java描述如下：

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static List<Integer> solveTwoSum(List<Integer> list, Integer target) {
        // compare的语法自从java7开始支持
        // lambda表达式的语法自从java8开始支持
        list.sort((a, b) -> Integer.compare(a, b));
        // System.out.println(list);
        Integer left = 0;
        Integer right = list.size() - 1;
        while (left < right) {
            Integer tmp = list.get(left) + list.get(right);
            if (tmp < target) {
                left += 1;
            } else if (tmp > target) {
                right -= 1;
            } else {
                return List.of(left, right);
            }
        }
        return List.of(-1, -1);
    }

    public static void main(String[] args) {
        // List.of的语法自从java9开始支持
        List<Integer> list = new ArrayList<>();
        List<Integer> ans;
        Integer target;

        list.clear();
        list.addAll(List.of(1, 2, 3));
        target = 5;
        ans = solveTwoSum(list, target);
        System.out.println(ans);

        list.clear();
        list.addAll(List.of(1, 2, 4, 8, 16, 32));
        target = 25;
        ans = solveTwoSum(list, target);
        System.out.println(ans);
    }
}

证明：

设左指针右移操作为，设右指针左移操作为，那么双指针算法会在最多次操作之内找到。显然包含在之中，或包含在之中，对于这两种情况，分别经过一次操作与一次操作之后可以找到。同理，也包含在或者中，对于这两种情况，分别经过一次操作与一次操作之后可以找到。以此类推，经过多次操作或者操作之后，总能找到。