三数之和

 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

func threeSum(nums []int) [][]int {
	var r [][]int
	L := len(nums)

	if L <= 0 {
		return r
	}

	for i := 0; i < L; i++ {
		min := i
		for j := i; j < L; j++ {
			if nums[j] < nums[min] {
				min = j
			}
		}
		t := nums[i]
		nums[i] = nums[min]
		nums[min] = t
	}

	if nums[0] > 0 || nums[L-1] < 0 {
		return r
	}

	for i := 0; i < L; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < L; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			left := nums[i] + nums[j]
			for k := L - 1; k > j; k-- {
				if k < L-1 && nums[k] == nums[k+1] {
					continue
				} else if nums[k]+left < 0 {
					break
				} else if nums[k]+left == 0 {
					r = append(r, []int{nums[i], nums[j], nums[k]})
					break
				}
			}
		}
	}
	return r
}

 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

func threeSum(nums []int) [][]int {
	var res [][]int
	L := len(nums)

	if L < 3 {
		return res
	}

	for i := 0; i < L; i++ {
		min := i
		for j := i; j < L; j++ {
			if nums[j] < nums[min] {
				min = j
			}
		}
		t := nums[i]
		nums[i] = nums[min]
		nums[min] = t
	}

	if nums[0] > 0 || nums[L-1] < 0 {
		return res
	}

	for i := 0; i < L; i++ {
		target := nums[i]
		if target > 0 {
			break
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue // 去重
		}
		l, r := i+1, L-1
		for l < r {
			sum := nums[l] + nums[r] + target

			if sum > 0 {
				r--
			} else if sum < 0 {
				l++
			} else if sum == 0 {
				res = append(res, []int{target, nums[l], nums[r]})
				l++
				r--
				// 去重
				for l < r && nums[l] == nums[l-1] {
					l++
				}
				for l < r && nums[r] == nums[r+1] {
					r--
				}
			}
		}
	}
	return res
}