本文共 1957 字，大约阅读时间需要 6 分钟。

题目描述：

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

题目没有说等于target的数对是否唯一，如果唯一，就是leetcode 167

然而我也没有主动和面试官沟通题目，是否唯一，是否有重复的数，自己随手写了个数组{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
   
     m) {				end--;			} else if(a[start]+a[end] < m) {				start++;			}		}	}}
   

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

这几个索引对，但他需要的是所有的组合数，（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
   
    0&&a[end-1]==a[end]){					System.out.println(start+","+(end-1));					counts++;					end--;				}				end+=counts;				int counte=0;				while(start
    
      m) {				end--;			} else if(a[start]+a[end] < m) {				start++;			}		}	}}
    
   

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

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

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

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

​private static void find2(int[] a, int m) {	int start = 0;	int end = a.length-1;	while(start
   
    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++;		}	}}
   

转载地址：http://tldgj.baihongyu.com/