15.三数之和

leetcode链接：
https://leetcode.cn/problems/3sum/

方案一

暴力求解
结果：有重复解，后期也一定会时间超时

List<List<Integer>> result1 = new ArrayList<>();

for (int i = 0; i < nums.length - 2; i++) {
	for (int j = i + 1; j < nums.length - 1; j++) {
		for (int j2 = j + 1; j2 < nums.length; j2++) {
			if (nums[i] + nums[j] + nums[j2] == 0) {
				List<Integer> le = new ArrayList<>();
				le.add(nums[i]);
				le.add(nums[j]);
				le.add(nums[j2]);
				result1.add(le);
			}
		}
	}
}

return result1;

方案二

先进行排序，再判断

结果： 超时

List<List<Integer>> result1 = new ArrayList<>();

Arrays.sort(nums);

for (int i = 0; (nums[i] < 1 && i < nums.length - 2); i++) {

	// 第二轮循环

	for (int j = i + 1; j < nums.length - 1; j++) {
		if (i!=0 && nums[i] == nums[i -1])
			break;

		// 第三轮循环
		for (int j2 = j + 1; j2 < nums.length; j2++) {

			if (j!=i + 1 && (nums[j] == nums[j -1]))
				break;

			if (nums[i] + nums[j] + nums[j2] == 0) {

				if (j2!=j + 1 && nums[j2] == nums[j2 -1])
					break;

				// 添加正确答案
				List<Integer> le = new ArrayList<>();
				le.add(nums[i]);
				le.add(nums[j]);
				le.add(nums[j2]);
				result1.add(le);
			}
		}
	}
}

return result1;

方案三

根据题解得：先进行排序，再使用指针

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result1 = new ArrayList<>();

        Arrays.sort(nums);

        int letf,right;
        for (int i = 0; (nums[i] < 1 && i < nums.length - 2); i++) {
            if (i!=0 && nums[i] == nums[i -1])
                continue;
            letf = i + 1;
            right = nums.length - 1;
            while (letf < right) {
                if (nums[right] + nums[letf] > -nums[i]){
                    right--;
                } else if (nums[right] + nums[letf] == -nums[i]) {
                    // 添加正确答案
                    List<Integer> le = new ArrayList<>();
                    le.add(nums[i]);
                    le.add(nums[letf]);
                    le.add(nums[right]);
                    result1.add(le);
                    while(nums[right] == nums[--right]) {
                        if (right == 0)
                            break;
                    }
                    while(nums[letf] == nums[++letf]) {
                        if (letf == nums.length - 1)
                            break;
                    }

                } else {
                    letf ++;
                }
            }
        }

        return result1;
    }
}

结果

解答成功:
执行耗时:27 ms,击败了95.35% 的Java用户
内存消耗:50.4 MB,击败了9.59% 的Java用户

几乎最优方案

https://leetcode.cn/problems/3sum/solution/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/

class Solution {
    //定义三个指针，保证遍历数组中的每一个结果
    //画图，解答
    public List<List<Integer>> threeSum(int[] nums) {
        //定义一个结果集
        List<List<Integer>> res = new ArrayList<>();
        //数组的长度
        int len = nums.length;
        //当前数组的长度为空，或者长度小于3时，直接退出
        if(nums == null || len <3){
            return res;
        }
        //将数组进行排序
        Arrays.sort(nums);
        //遍历数组中的每一个元素
        for(int i = 0; i<len;i++){
            //如果遍历的起始元素大于0，就直接退出
            //原因，此时数组为有序的数组，最小的数都大于0了，三数之和肯定大于0
            if(nums[i]>0){
                break;
            }
            //去重，当起始的值等于前一个元素，那么得到的结果将会和前一次相同
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int l = i +1;
            int r = len-1;
            //当 l 不等于 r时就继续遍历
            while(l<r){
                //将三数进行相加
                int sum = nums[i] + nums[l] + nums[r];
                //如果等于0，将结果对应的索引位置的值加入结果集中
                if(sum==0){
                    // 将三数的结果集加入到结果集中
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //在将左指针和右指针移动的时候，先对左右指针的值，进行判断
                    //如果重复，直接跳过。
                    //去重，因为 i 不变，当此时 l取的数的值与前一个数相同，所以不用在计算，直接跳
                    while(l < r && nums[l] == nums[l+1]) {
                        l++;
                    }
                    //去重，因为 i不变，当此时 r 取的数的值与前一个相同，所以不用在计算
                    while(l< r && nums[r] == nums[r-1]){
                        r--;
                    } 
                    //将 左指针右移，将右指针左移。
                    l++;
                    r--;
                    //如果结果小于0，将左指针右移
                }else if(sum < 0){
                    l++;
                    //如果结果大于0，将右指针左移
                }else if(sum > 0){
                    r--;
                }
            }
        }
        return res;
    }
}