如何求数组中两两相加等于max的组合种数

1. 问题描述

给定一个数组[7,3,4,8,1], max=9

这个数组中满足条件的组合为8,1

则输出 8,1

2.问题解析

方法1：“蛮力”法

两重循环判断两个数的和是否为max，时间复杂度为O(n²)

方法2：排序法

先对数组元素进行排序，此算法的时间复杂度为O(nlogn)，对排序后的数组分别从前到后和从后向前遍历，当满足a[start]+a[end]>max ，如果存在两个数的和等于max则一定在[start,end+1]之间，当满足a[start]+a[end]<max ，如果存在两个数的和等于max则一定在[start+1,end]之间.

3.代码

import java.util.Arrays;


public class 求数组中两两相加等于20的组合种数 {
	//蛮力法
	public static String findSumNumber(int []a,int max){
		for(int i=0;i<a.length;i++){
			for(int j=i;j<a.length;j++){
				if(a[i]+a[j]==max){
					return a[i]+" "+a[j];
				}
			}
		}
		return null;
	}
	//排序法
	public static void findSumNumber1(int []a,int max){
		Arrays.sort(a);
		int start=0;
		int end=a.length-1;
		while(start<end){
			if(a[start]+a[end]>max){
				end--;
			}
			else if(a[start]+a[end]<max){
				start++;
			}else{
				System.out.println(a[start]+" "+a[end]);
				start++;
				end--;
			}
			
			
		}
		
	}

	public static void main(String[] args) {
		int []a=new int[]{7,3,4,8,1};
		System.out.println(findSumNumber(a, 9));
		findSumNumber1(a, 9);
	}
	

}