一.题目内容:对已排序的数组进行2-Sum 二.实现方式: 对数组进行排序，分别设置两个指针在数组头部和尾部，将两个数相加，观察相加后的结果: 1. 如果结果大于0,说明右边元素的绝对值大于左边元素的绝对值，则右边的指针-1. 2. 如果结果小于0， 说明左边元素的绝对值大于右边元素的绝对值，则左边的指针+1. 3. 如果结果等于0，则需要找到数组中有多少和左边元素和右边元素相同的元素，然后利用排列组合公式得到有多少对组合. 三.实现方法:
public static int doTwoSumFaster(int[] a){ int count = 0; Arrays.sort(a); int i = 0; int j = a.length-1; while(i!=j && a[i]<=0 && a[j]>=0){ int result = a[i]+a[j]; if(result > 0){ j--; }else if(result<0){ i++; }else{ int lo = i; int hi = j; int lc = 1; int rc = 1; while(a[++i] == a[lo]){ lc++; } while(a[--j] == a[hi]){ rc++; } count+=lc*rc; } } return count; }新闻热点
疑难解答
