java实现和为定值的两个数

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1 问题描述

输入一个整数数组和一个整数，在数组中查找两个数，满足他们的和正好是输入的那个整数。如果有多对数的和等于输入的整数，输出任意一对即可。例如，如果输入数组[1,2,4,5,7,11,15]和整数15，那么由于4+11 = 15，因此输出4和11。

2 解决方案

2.1 排序夹逼法

首先将整数数组，使用合并排序进行从小打到的排序，然后对这个排完序的数组从两头往中间遍历，一旦出现两个数的和等于输入的那个整数，则立即输出这两个数，并结束遍历。

package com.liuzhen.array_2;public class TwoSumN { /* * 参数A：给定的一个从小到大排序的数组 * 参数n:待求和数n * 函数功能：打印出A中两个元素，满足A[i]+A[j] = n */ public void getTwoSumN(int[] A,int n){ int start = 0; int end = A.length - 1; while(start < end){ if(A[start] + A[end] == n){ System.out.println("\n数组中元素A["+start+"]" + " + A["+end+"] = "+n+",A["+start+"] = "+A[start]+",A["+end+"] = "+A[end]); break; } else{ if(A[start] + A[end] > n) end--; else start++; } } } //归并排序 public void mergeSort(int[] A){ if(A.length > 1){ int[] leftA = getHalfArray(A,0); //数组A的左半部分 int[] rightA = getHalfArray(A,1); //数组A的右半部分 mergeSort(leftA); mergeSort(rightA); getMerge(A,leftA,rightA); } } /* * 参数A：要进行折半的数组 * 参数judge:judge == 0表示返回数组A左上半部分，judge != 0表示返回数组A的右半部分 * 函数功能：把数组按照长度均分为上半部分和下半部分 */ public int[] getHalfArray(int[] A,int judge){ int[] result; if(judge == 0){ result = new int[A.length/2]; for(int i = 0;i < A.length/2;i++) result[i] = A[i]; } else{ result = new int[A.length - A.length/2]; for(int i = 0;i < A.length - A.length/2;i++) result[i] = A[i+A.length/2]; } return result; } /* *参数A：给定待排序数组 *参数leftA:数组A的左半部分 *参数rightA:数组的右半部分 *函数功能：返回数组A的从小到大排序 */ public void getMerge(int[] A,int[] leftA,int[] rightA){ int i = 0; //用于计算当前遍历leftA的元素个数 int j = 0; //用于计算当前遍历rightA的元素个数 int count = 0; //用于计算当前得到按从小到大排序的A的元素个数 while(i < leftA.length && j < rightA.length){ if(leftA[i] < rightA[j]){ A[count++] = leftA[i]; i++; } else{ A[count++] = rightA[j]; j++; } } if(i < leftA.length){ while(i < leftA.length) A[count++] = leftA[i++]; } if(j < rightA.length){ while(j < rightA.length) A[count++] = rightA[j++]; } } public static void main(String[] args){ TwoSumN test = new TwoSumN(); int[] A = {2,1,7,4,6,1,2,4,3,6,8,4,2,1,7,3,4,6,8,3,4}; test.mergeSort(A); System.out.println("对数组A进行合并排序后结果："); for(int i = 0;i < A.length;i++) System.out.print(A[i]+" "); test.getTwoSumN(A, 10); } }