leetcode/3Sum/ThreeSum.java at master · mirraico/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
package com.mirraico.leetcode;

import java.util.*;

public class ThreeSum {

	public void quickSort(int[] nums, int s, int e) {
		if(e - s <= 1) return;
		int mid = nums[s], tmp;
		int i = s, j = e - 1;
		while(i != j) {
			for(; j != i; j--) {
				if(nums[j] < mid) {
					tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
					break;
				}
			}
			for(; i != j; i++) {
				if(nums[i] > mid) {
					tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
					break;
				}
			}
		}
		quickSort(nums, s, i);
		quickSort(nums, i + 1, e);
	}

	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> ans = new ArrayList<>();
		this.quickSort(nums, 0, nums.length);
		for(int i = 0; i < nums.length; i++) {
			if(i > 0 && nums[i] == nums[i-1]) continue;
			int target = nums[i];
			int p = i + 1, q = nums.length - 1;
			while(p < q) {
				if(p > i + 1 && nums[p] == nums[p-1]) {
					p++;
					continue;
				}
				if(q < nums.length - 1 && nums[q] == nums[q+1]) {
					q--;
					continue;
				}
				if(nums[p] + nums[q] == -target) {
					List<Integer> tmpList = new ArrayList<>();
					if(i < p) {
						tmpList.add(nums[i]);
						tmpList.add(nums[p]);
						tmpList.add(nums[q]);
					} else if(i > q) {
						tmpList.add(nums[p]);
						tmpList.add(nums[q]);
						tmpList.add(nums[i]);
					} else {
						tmpList.add(nums[p]);
						tmpList.add(nums[i]);
						tmpList.add(nums[q]);
					}
					ans.add(tmpList);
				}
				if(nums[p] + nums[q] > -target) q--;
				else p++;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		int[] nums = {-1, -1, -1, -1, 2, 2, 2};
		System.out.println(new Solution().threeSum(nums));
	}

}