LeetCode/Solution015.java at master · jyneo/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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
public class Solution{

    // Approach #1 (Brute Force)
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> result= new ArrayList<List<Integer>>();
        if (nums.length < 3 || nums == null) {
            return result;
        }
        Arrays.sort(nums); //数组排序
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>(); // 插入代码出错

        for (int i = 0; i < nums.length; i++) { //将数组存入hashmap
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length - 2; i++) {
            if (i==0 || nums[i] != nums[i - 1]) { //处理第一层遍历nums[i]的重复
                for (int j = i + 1; j < nums.length - 1; j++) {
                    int complement = sum - nums[i] - nums[j];
                    if (map.containsKey(complement) && map.get(complement) > j) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(complement);
                        result.add(list);
                    }
                    while(nums[j] == nums[j + 1] && j < nums.length - 2){
                        j++; //处理第二层遍历nums[j]的重复
                    }
                }
            }
        }
        return result;
    }

    // Approach #2 (Sorting With Two Pointers)
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums.length < 3 || nums == null) {
            return result;
        }
        Arrays.sort(nums); //数组排序
        for (int i = 0; i < nums.length - 2; i++) {
            if(i == 0 || nums[i] != nums[i - 1]){ // 处理nums[i]的重复
                int low = i + 1;
                int high = nums.length - 1;
                while(low < high){
                    int sum = nums[i] + nums[low] + nums[high];
                    if (sum == 0) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[i]);
                        list.add(nums[low]);
                        list.add(nums[high]);
                        result.add(list);
                        low++;
                        high--;
                        while (low < high && nums[low] == nums[low - 1]) {
                            low++; //处理nums[low]的重复
                        }
                        while (low < high && nums[high] == nums[high + 1]) {
                            high--; //处理nums[high]的重复
                        }
                    }else if (sum > 0) {
                        high--;
                    }else
                        low++;
                }
            }
        }
        return result;
    }

    // Approach #3 (HashSet)
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums.length < 3 || nums == null) {
            return result;
        }
        HashSet<List<Integer>> hash = new HashSet<List<Integer>>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            //这种处理重复元素的方式比较容易理解
            if(i > 0 || nums[i] == nums[i - 1])
                continue;
            int low = i + 1;
            int high = nums.length - 1;
            while(low < high){
                int sum = nums[i] + nums[low] + nums[high];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[low]);
                    list.add(nums[high]);
                    if (!hash.contains(list)) {
                        hash.add(list);
                        result.add(list);
                    }
                    low++;
                    high--;
                }else if (sum < 0) {
                    low++;
                }else
                    high--;
                }
        }
        return result;
    }

    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums.length < 3 || nums == null) {
            return result;
        }
        HashSet<List<Integer>> hash = new HashSet<List<Integer>>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            //另一种处理重复元素的方法
            if(i == 0 || nums[i] != nums[i - 1]){
                int low = i + 1;
                int high = nums.length - 1;
                while(low < high){
                    int sum = nums[i] + nums[low] + nums[high];
                    if (sum == 0) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[i]);
                        list.add(nums[low]);
                        list.add(nums[high]);
                        if (!hash.contains(list)) {
                            hash.add(list);
                            result.add(list);
                        }
                        low++;
                        high--;
                    }else if (sum < 0) {
                        low++;
                    }else
                        high--;
                    }
                }
            }
        return result;
    }
}