LeetCode（923 三数之和各种可能）

如题
与之前那个三数之和的可能序列有异曲同工之妙，但是那个是需要去重，这个则需要计算全部可能。那么先用相似的双指针法来实现

	public static int threeSumMulti(int[] A, int target) {
		double count = 0;  
		if (A == null || A.length < 3) {
			return (int)count;
		}
		Arrays.sort(A);
		for (int i = 0; i < A.length - 2; i++) {
			if (A[i] > target) {   //同样的退出条件
				break;
			}
			int m = i + 1;
			int n = A.length - 1;
			int flagm = 0;   //前面存在的相同元素个数
			int flagn = 0;	//后面存在的相同元素个数
			while (m < n) {
				if (A[i] + A[m] + A[n] < target) {  //和值小于目标则m++
					m++;
				} else if (A[i] + A[m] + A[n] > target) { //大于目标则n--
					n--;
				} else {
					if (A[m + 1] == A[m]) {  //元素相同则计数+1
						flagm++;
						m++;
					} else if (A[n - 1] == A[n]) {
						flagn++;
						n--;
					} else {	//不存在相同元素则计算当前次数
						count = count + (flagm + 1) * (flagn + 1); //+的1为当前元素   
						flagm = 0;		//注意归零计数
						flagn = 0;
						m++;
						n--;
					}
				}
			}
			if (flagm != 0 || flagn != 0) {  //应对由元素相等的退出条件
				if (A[m] == A[n]) {//对应的是两个指针指向相同元素的特殊情况  
					count = count + (flagm+1)*flagm/2;  //优先flagm计数，所以n必然为1。则该段总计flagm+1个相同元素
				} else {	//单指针检索相同情况  注意区分各种情况 00x 0xx 00xx
					count = count + (flagn != 0 ? flagm + 1 : flagm) * (flagm != 0 ? flagn + 1 : flagn);
				}
			}
		}		 
		return (int) (count % (Math.pow(10, 9) + 7));//注意小心越界
	}

实现是没问题，但是结果
过于耗时，稍加分析，很显然时间消耗点在于各种相同元素的检索上，那么优化的大方向就有了，尽可能压缩这种重复操作。采取缓存与数学运算相结合的方法进行优化