一.题目内容: 对已排序数组进行 three-sum-faster 二.实现方式: 首先将数组进行排序，然后设置三个指针，位置为数组头部(lo)，数组尾部(hi)和数组尾部-1(k),然后计算三个数相加的结果: 1.如果相加的结果大于0，则说明右边的两个数之和明显大于左边的，则将k–. 2.如果相加的结果小于0，则说明左边的数负的太厉害，所以lo++. 3.如果相加结果为0，则要找到有多少三个相同的pair然后计算有多少种排列组合. 4.完成一次k的循环以后，还要将lo=0,hi–,k=hi-1.
public static int threeSumFaster(int[] a){ int count = 0; Arrays.sort(a); int lo = 0; int hi = a.length-1; int k = hi-1; while(a[hi]>0){ while(k>lo){ int result = a[lo]+a[hi]+a[k]; if(result>0){ k--; }else if(result<0){ lo++; }else{ count++; int sl = lo; int sk = k; while(a[++lo] == a[sl] && lo<k){ count++; } while(a[--k] == a[sk] && k>sl){ count++; } } } hi--; k=hi-1; lo = 0; } return count; }新闻热点
疑难解答
