【Lintcode】609. Two Sum - Less than or equal to target

题目地址：

https://www.lintcode.com/problem/two-sum-less-than-or-equal-to-target/description

给定一个整数数组$A$A，再给定一个数target，求数组中有多少对数之和小于等于target。

思路是先排序，然后用对撞双指针，设左指针为$i$i，右指针为$j$j，同时比较两数之和与target的关系，并且累加结果。如果和大于target，那么就左移$j$j；否则，说明$A[i]$A[i]和$A[i+1],A[i+2],...,A[j]$A[i+1],A[i+2],...,A[j]之和都满足条件，就将$j-i$j−i累加到结果中，同时右移$i$i。如此这样，直到两个指针相遇。代码如下：

import java.util.Arrays;

public class Solution {
    /**
     * @param nums: an array of integer
     * @param target: an integer
     * @return: an integer
     */
    public int twoSum5(int[] nums, int target) {
        // write your code here
        if (nums == null || nums.length < 2) {
            return 0;
        }
        
        Arrays.sort(nums);
        int res = 0;
        
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int sum = nums[i] + nums[j];
            if (sum > target) {
                j--;
            } else {
                res += j - i;
                i++;
            }
        }
        
        return res;
    }
}

时间复杂度$O(n\log n)$O(nlogn)，空间$O(1)$O(1)。

算法正确性证明：
数学归纳法。设算法对数组长度为$k$k时是正确的，当数组长度为$k+1$k+1时，考虑计算$A[i,j]$A[i,j]（$i<j$i<j）这个片段满足条件的数对个数。我们先考虑含$A[i]$A[i]或$A[j]$A[j]的满足条件的数对个数。如果$A[i]+A[j]>target$A[i]+A[j]>target，那么$A[i,j]$A[i,j]这个片段里含$A[j]$A[j]的所有数对都不满足条件，所以满足条件的数对个数等于$A[i,j-1]$A[i,j−1]这个片段里满足条件的数对，根据归纳假设，算法可以算出，结论正确；如果$A[i]+A[j]\le target$A[i]+A[j]≤target，那么$A[i,j]$A[i,j]这个片段里含$A[i]$A[i]的所有数对都满足条件，所以此时满足条件的数对个数等于$j-i$j−i加上$A[i+1,j]$A[i+1,j]这个片段里满足条件的数，根据归纳假设，算法可以算出，结论正确。综上，算法正确。