TWO SUM算法

声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
给定N个不同的数A[0...N-1]以及某定值sum, 找到这N个数中的两个数，使得它们的和为sum.
如给定数组：{0,4,3,7,9,11,14,16,17}, sum = 20, 返回(3,17),(4,16),
(9,11)
一、暴力求解，时间复杂度O(N*N), 空间复杂度O(1)
二、稍微好一点的算法，先排序，时间复杂度（O(Nlog(N)），两头扫时间复杂度O（N），最终时间复杂度为O(Nlog(N) + N) = O(Nlog(N))
两头扫：
令：i=0;j=n-1; 判断a[i]+a[j]是否等于sum
1、如果小于，i++
2、如果大于，j--
3、如果等于，i++， j--，直到i==j退出循环
Java实现如下

package com.mystudy.algorithm;

import java.util.Arrays;
/**
 * TwoSum算法，在一个数组中两个数的和等于一个定值
 * @author 
 *
 */
public class TwoSum {

    public static void main(String[] args) {
        int a[] = {0,4,3,7,9,11,14,16,17};
        Arrays.sort(a);
        twoSum(a, 20);
    }

    public static void twoSum(int a[], int sum){
        int i = 0;
        int j = a.length - 1;
        while(i<j){
            if (a[i] + a[j] < sum) {
                i++;
            }else if (a[i] + a[j] > sum) {
                j--;
            }else {
                System.out.println(a[i] + "--->>>" + a[j]);
                i++;
                j--;
            }
        }
    }
}

输出结果：
3--->>>17
4--->>>16
9--->>>11