package test.algorithm;
import java.util.Arrays;
import java.util.HashSet;
/**
* 三数之和问题
*
* @author CaiHao
* @since 2022/3/22 19:44
*/
public class SumOfThree {
/**
* 问题描述：
* 现有一个数，问数组中是否有三个数之和，与之相等
*
*/
public static void main(String[] args) {
int[] a = {2, 5, 8, 27, 13, 36};
// 多个数来验证结果
int[] sums = {12, 22, 23, 27, 32, 42, 57};
Boolean hasResult;
for (int i = 0; i < sums.length; i++) {
hasResult = solution1(a, sums[i]);
System.out.println(sums[i] + ":" + hasResult);
}
}
/**
* 三重循环·1
* 特点：复杂度过高，不推荐
* 时间复杂度O(n^3)，空间复杂的O(1)
*
* @param a
* @param sum
* @return Boolean
*/
private static Boolean solution1(int[] a, int sum) {
int total;
for (int i = 0; i < a.length - 2; i++) {
for (int j = i + 1; j < a.length - 1; j++) {
for (int k = j + 1; k < a.length; k++) {
total = a[i] + a[j] + a[k];
if (sum == total) {
return true;
}
}
}
}
return false;
}
/**
* 双指针·2
* 特点：循环少、性能好、需对数组排序
* 时间复杂度O(n^2)，空间复杂的O(1)
*
* @param a
* @param sum
* @return Boolean
*/
private static Boolean solution2(int[] a, int sum) {
Arrays.sort(a);
// 低指针
int LowPointer;
// 高指针
int HighPointer;
// 总值
int total;
for (int i = 0; i < a.length - 2; i++) {
LowPointer = i + 1;
HighPointer = a.length - 1;
// 核心：当前值固定，高值或低值移动，三值相加与sum比较
while (HighPointer > LowPointer) {
total = a[i] + a[LowPointer] + a[HighPointer];
if (total == sum) {
return true;
}
// 值过大时，高值的指针左移
else if (total > sum) {
HighPointer--;
}
// 值过小时，低值的指针右移
else if (total < sum) {
LowPointer++;
}
}
}
return false;
}
/**
* HashSet方案·3
* 特点：性能较好，保留原有数组顺序
* 时间复杂度O(n^2)，空间复杂的O(n)
*
* @param a
* @param sum
* @return Boolean
*/
private static Boolean solution3(int[] a, int sum) {
HashSet<Integer> set = new HashSet<Integer>();
int remain;
int last;
for (int i = 0; i < a.length - 1; i++) {
set.clear();
// 剩下两个值的和
remain = sum - a[i];
for (int j = i + 1; j < a.length; j++) {
// 需要的最后一个值
last = remain - a[j];
// 需要的值在set集合出现过，则找到
if (set.contains(last)) {
return true;
}
set.add(a[j]);
}
}
return false;
}
}
