算法之ThreeSum篇

标签：arch   href   binary   top   方法   java   三元   pointer   错误   

topic：ThreeSum
目标：用于统计一个数组中和为 0 的三元组数量，每个三元组都不重复

方法

• 方法一：最简单方法
• 方法二：先排序，对两元素求和，再用二分查找寻找相反数
• 方法三：先排序，再用左右两指针查找一个数的相反数

方法一：最简单方法

public class ThreeSumSlow implements ThreeSum{
	
	@Override
	public int count(int[] shuzu)  {
		int c = 0; //次数
		for(int i = 0; i 

方法二：先排序，对两元素求和，再用二分查找寻找相反数

注意：数组中不能有重复元素

import java.util.Arrays;

public class ThreeSumBinarySearch implements ThreeSum{
	
	@Override
	public int count(int[] shuzu) {
		//先排序
		Arrays.sort(shuzu);
		int len = shuzu.length;
		int c = 0;
		int negSum;
		int index; //找到的相反数的下标
		//先对两个元素求和，再找有没有和的相反数的数
		for(int i = 0; i  j)  c ++;   //如果小于j，可能会重复计数！！！
			}
		}
		return c;
	}

}

方法三：先排序，再用左右两指针查找一个数的相反数

import java.util.Arrays;

public class ThreeSumTwoPointer {
	//先将数组排序，再设置双指针查找
	public int count(int[] shuzu) {
		Arrays.sort(shuzu);
		int N = shuzu.length;
		int c = 0; //count
		for(int i = 0; i  0 && shuzu[i] == shuzu[i-1]) continue; //若该数与上一个index的数相同，则跳过。因为已经考虑过这种情况了
			int l = i+1;
			int r = N-1;
			int target = -shuzu[i];
			while(l

算法之ThreeSum篇

标签：arch   href   binary   top   方法   java   三元   pointer   错误   

原文地址：https://www.cnblogs.com/Cindy-H/p/13635063.html