LeetCode/src/medium/ThreeSum.java at master · chenyiAlone/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
package medium;

import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import static util.Utils.*;

/**
 *
 * ClassName: ThreeSum
 * @author chenyiAlone
 * Create Time: 2018/11/30 12:26:28
 * Description: No.15 勉强通过，时间复杂度太差
 * Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

    Note:

    The solution set must not contain duplicate triplets.

    Example:

    Given array nums = [-1, 0, 1, 2, -1, -4],

    A solution set is:
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]
 * *********************************
 * update 2019/1/17:
 *  1. 将数组首先进行排序
 *  2. 使用双指针lo, hi双向扫描，while将相同结果跳过
 */
public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        printArray(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];
            while (lo < hi) {
                if (nums[lo] + nums[hi] == sum) {
                    res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                    lo++;
                    hi--;
                } else if (nums[lo] + nums[hi] < sum) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }
        return res;
    }

	public List<List<Integer>> threeSum_Low(int[] nums) {
	    Arrays.sort(nums);
		int lo = 0, hi = nums.length - 1;
		List<List<Integer>> ans = new ArrayList<>();
		printArray(nums);
		for (int i = 0; i < nums.length - 2; i++) {
		    if (i > 0 && nums[i] == nums[i-1]) continue;
			for (int j = i + 1; j < nums.length - 1; j++) {
				int seek = -(nums[i] + nums[j]);
				lo = j + 1;
				hi = nums.length - 1;
				int mid = 0;
				boolean hasTriplets = false, hasRep = false;
				while (lo <= hi) {
					mid = (lo + hi) / 2;
					if 		(nums[mid] < seek) lo = mid + 1;
					else if (seek < nums[mid]) hi = mid - 1;
					else { hasTriplets = true; break; }
				}
				if (hasTriplets) {

                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[mid]);
                    if (ans.size() == 0) {
                        ans.add(list);
                    } else if (!ans.get(ans.size() - 1).equals(list)) {
                        ans.add(list);
                    }
				}
			}
		}
		return ans;
	}
	public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        int[] nums2 = {-2, 0, 1, 1, 2};
        System.out.println(new ThreeSum().threeSum(nums2));
    }

}