LeetCode/ThreeSum.java at master · Orio77/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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;


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

        // Create solution list
        List<List<Integer>> solutionList = new ArrayList<>();
        // Sort nums
        Arrays.sort(nums);
        // Create 3 pointers
        int i = 0;
        int j = nums.length - 1;
        int k = 0;
        // Iterate over all elements
        while (i < j) {
            if (nums[i] + nums[j] > 0) {
                k = i+1;
                while (k < j && nums[i] + nums[j] + nums[k] <= 0) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> sol = new ArrayList<>();
                        sol.add(nums[i]);
                        sol.add(nums[j]);
                        sol.add(nums[k]);
                        solutionList.add(sol);
                        break;
                    }
                    k++;
                }
            }
            else if (nums[i] + nums[j] < 0) {
                k = j-1;
                while (k > i && nums[i] + nums[j] + nums[k] >= 0) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> sol = new ArrayList<>();
                        sol.add(nums[i]);
                        sol.add(nums[j]);
                        sol.add(nums[k]);
                        solutionList.add(sol);
                        break;
                    }
                    k--;
                }
            }
            else if (nums[i] + nums[j] == 0) {
                k = i+1;
                while (k < j && nums[k] <=0) {
                    if (nums[k] == 0) {
                        List<Integer> sol = new ArrayList<>();
                        sol.add(nums[i]);
                        sol.add(nums[j]);
                        sol.add(nums[k]);
                        solutionList.add(sol);
                        break;
                    }
                    k++;
                }
            }

            if (i % 2 == 0) {
                i++;
            }
            else {
                j--;
            }
        }


        // Make Soulutions distinct
        Set<String> set = new HashSet<>();
        List<List<Integer>> toRemove = new ArrayList<>();
        for (List<Integer> list : solutionList) {
            list.sort(Comparator.naturalOrder());
            String curNumSeq = list.get(0) + ";" + list.get(1) + ";" +  list.get(2);
            if (!set.add(curNumSeq)) {
                toRemove.add(list);
            }
        }
        for (List<Integer> list : toRemove) {
            solutionList.remove(list);
        }
        return solutionList;
    }
}


class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int target = 0;
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<>();
        List<List<Integer>> solution = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            int j = i+1;
            int k = nums.length - 1;

            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == target) {
                    set.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                }
                else if (sum < target) {
                    j++;
                }
                else {
                    k--;
                }
            }
        }
        solution.addAll(set);
        return solution;
    }
}