面试题-排序数组中找两数之和为target的所有数的组合-leetcode167的变型题

题目描述：

给定排序数组arr，目标值target，寻找数组中所有和为target的数的组合，返回对应的索引。

题目没有说等于target的数对是否唯一，如果唯一，就是leetcode 167https://blog.****.net/orangefly0214/article/details/89155613

然而我也没有主动和面试官沟通题目，是否唯一，是否有重复的数，自己随手写了个数组{1,2,3,4,5}，target=7，这样的话，满足条件的就有2对了，

所以题目变形为：

给定排序数组arr，目标值target，寻找数组中所有和为target的数的组合。（数组中和为target的数对不唯一，且数组中没有重复的元素。）

此时的解法：

排序数组，想到的就是二分查找，所以预设两个指针，从两边向中间扫描，每扫描到一对，打印，

public class twoSumComba {
	public static void main(String[] args) {
		int[] a = {1,2,3,4,5};
		int m = 7;
		find(a,m);
	}
	private static void find(int[] a, int m) {
		int start = 0;
		int end = a.length-1;
		while(start<end) {
			if(a[start]+a[end] == m) {
				System.out.println(start+","+end);
				start++;
				end--;
			} else if(a[start]+a[end] > m) {
				end--;
			} else if(a[start]+a[end] < m) {
				start++;
			}
		}
	}
}

但是！！！重点来了，当我写出上面的代码时，面试官问我说，如果有两个2和两个5呢？我一脸懵逼。用上面的方法只能返回

面试题-排序数组中找两数之和为target的所有数的组合-leetcode167的变型题

这几个索引对，但他需要的是所有的组合数，（1,6），（1,5），（2,6），（2,5）即2,2,5,5对应下标的组合。

陷入沉思，没想出来。

回来以后考虑了下，写出了一种这样的方法，测试了一下暂时发现应该没问题。

思路：当遇到两数之和与target相等时，判断start的后面是否有与它相等的，如果有，则继续打印start++和end,直到没有。在这个过程中做计数，判断完之后指针回溯到之前start的值。

同理，判断end之前是否有与它相等的，若有，则继续打印start和end--，直到没有，同时计数（看有多少个重复的数），结束之后指针回溯之前的位置。

然后继续正常的操作。（我这个也是个神思路啊，上网也没查到别的方法，自己创造的）

public class twoSumComba {
	public static void main(String[] args) {
		int[] a = {1,2,2,2,3,4,5,5};
		int m = 7;
		find(a,m);
	}
	private static void find(int[] a, int m) {
		int start = 0;
		int end = a.length-1;
		while(start<end) {
			if(a[start]+a[end] == m) {
				System.out.println(start+","+end);
				int counts=0;
				while(end>0&&a[end-1]==a[end]){
					System.out.println(start+","+(end-1));
					counts++;
					end--;
				}
				end+=counts;
				int counte=0;
				while(start<end&&a[start+1]==a[start]){
					System.out.println(start+1+","+end);
					counte++;
					start++;
				}
				start-=counte;				
				start++;
				end--;
			} else if(a[start]+a[end] > m) {
				end--;
			} else if(a[start]+a[end] < m) {
				start++;
			}
		}
	}
}

面试题-排序数组中找两数之和为target的所有数的组合-leetcode167的变型题

当时面完试我问面试官的时候，他说如果存在重复的数，就确定重复数的范围，然后组合打印，反正没太明白。

更新——————————————————————

在同学的耐心解答下，终于写出面试官提示的思路的方法：

如果i和j索引加起来不等于m，照常进行，当等于m的时候去找边界。找到边界后用两层for循环嵌套就可以


private static void find2(int[] a, int m) {
	int start = 0;
	int end = a.length-1;
	while(start<end) {
		if(a[start]+a[end] == m) {
			int f=start;
			while(f<end&&a[f+1]==a[f]){
				f++;//[start,f]重复的边界
			}
			int g=end;
			while(g>0&&a[g-1]==a[g]){
				g--;//[g,end]重复的边界
			}
			for(int i=start;i<=f;i++){
				for(int j=end;j>=g;j--){
					System.out.println(i+","+j);
				}
			}				
			start=f+1;;
			end=g-1;
		} else if(a[start]+a[end] > m) {
			end--;
		} else if(a[start]+a[end] < m) {
			start++;
		}
	}
}

面试题-排序数组中找两数之和为target的所有数的组合-leetcode167的变型题

题目描述：

所以题目变形为：

相关推荐