一个排好序的数组，找出两数之和为M的所有组合

网上看到这个面试题，自己琢磨了下，写了几个比较简单的解决方法，请各位大虾给出自己的理解，最好能给出更为简单的解决办法

 

 

package com.liuc.test;

//一个排好序的数组，找出两数之和为M的所有组合 这里设置M为100，可以将100替换为想要让求的和
public class SumM {

	public static int[] arr = { 1, 3, 5, 7, 9, 14, 23, 70, 80, 93, 95, 100,200, 300 };
	public static int count1 = 0;
	public static int count2 = 0;
	public static int count3 = 0;

	public static void main(String[] args) {
		// 1、纯for循环
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				count1++;
				if (arr[i] + arr[j] == 100) {
					System.out.println(arr[i] + ":" + arr[j]);
				}
			}
		}
		//卡住一个端，左端只有小于M/2才会判断
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] <= 100 / 2) {
				for (int j = i + 1; j < arr.length; j++) {
					count2++;
					if (arr[i] + arr[j] == 100) {
						System.out.println(arr[i] + ":" + arr[j]);
					}
				}
			}
		}
		//卡住一个端，左端只有小于M/2，右端大于M/2才会判断
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] <= 100 / 2) {
					for (int j = i + 1; j < arr.length; j++) {
						if (arr[j] >= 100 / 2) {
							count3++;
							if (arr[i] + arr[j] == 100) {
								System.out.println(arr[i] + ":" + arr[j]);
							}
					}

				}
			}
		}
		System.out.println("count1=" + count1);
		System.out.println("count2=" + count2);
		System.out.println("count3=" + count3);
	}

}

 

结果：

 

5:95

7:93

5:95

7:93

5:95

7:93

count1=91

count2=70

count3=49

 

 

 

 

评论

3 楼 kaqike 2013-07-22  

Sorry，实际计算和的次数为9

2 楼 kaqike 2013-07-22  

实际计算和的次数为7

1 楼 kaqike 2013-07-22  

/**
 * 
 * @author Kaqike
 *
 */
public class TestSequenceSum {
	public static int[] arr = { 1, 3, 5, 7, 9, 14, 23, 70, 80, 93, 95, 100,200, 300 };  
	public static int M =100;  
	public static void main(String[] args){
		 int  i = 0;
		 int j = arr.length-1;
		 int count =0;//求和的次数
		 while(i<j){
			 count++;
			 if(arr[j]>=M)  j--;
			 int sum =arr[i]+arr[j];
			 if(sum>M){
				 j--;
			 }else if(sum==M) {
				 System.out.println(arr[i]+"  "  +arr[j]);
				 i++;
				 j--;
			 }else{
				 if(sum<M) i++;
			 }
		 }
		 System.out.println("求和的次数为"+count);
	}
}