聲明： 本總結(jié)僅為個人學(xué)習(xí)總結(jié)拒炎，以防止遺忘而作瞄崇，不得轉(zhuǎn)載和商用窟绷。
給定N個不同的數(shù)A[0...N-1]以及某定值sum, 找到這N個數(shù)中的兩個數(shù)，使得它們的和為sum.
如給定數(shù)組：{0,4,3,7,9,11,14,16,17}, sum = 20, 返回(3,17),(4,16),
(9,11)
一、暴力求解劈猿，時間復(fù)雜度O(N*N), 空間復(fù)雜度O(1)
二沮榜、稍微好一點(diǎn)的算法尚胞，先排序签钩，時間復(fù)雜度（O(Nlog(N)），兩頭掃時間復(fù)雜度O（N）坏快，最終時間復(fù)雜度為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退出循環(huán)
Java實(shí)現(xiàn)如下
package com.mystudy.algorithm;
import java.util.Arrays;
/**
* TwoSum算法级及，在一個數(shù)組中兩個數(shù)的和等于一個定值
* @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--;
}
}
}
}
輸出結(jié)果：
3--->>>17
4--->>>16
9--->>>11
