未分類

3Sum

Array, Go, LeetCode, TwoPointers

3Sum

Given an array S of n integers, are there elements a, b, c in S 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.

For example:

1
2
3
4
5
6
7
Given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
提示 解題應用
Array 二維陣列
TwoPointers 記錄index位置

Default:

1
2
3
func threeSum(nums []int) [][]int {
}

解答思路:

正如預期暴力法是沒有辦法順利過關，然而要從一陣列中挑出3個總合正好為0的所有結果比起只挑兩個複雜太多，所以為了要讓事情變的簡單些我們就先將整個陣列做排序，接著就是依序來找3個總合，正如先前所說如果只有兩個的總合就簡單多了，因此每取一個就從該元素後頭的陣列找另外兩個對應的所有組合，好比我們拿了第一個元素，接著就從第2個~第n個找另外兩個的所有組合，而拿了第二個元素就從第3個~第n個找另外兩個的所有組合，好處在於事先排序能篩掉重覆的情況，如果拿的第一個元素為-1，第2~n個就會找出與-1對應的所有組合，而如果下一個元素還是-1，此時從第3~n個找出的所有組合，再與先前找的相比不但組合可能較少還有可能完全重覆，因此如果能事先做好排序便能大幅降低解題的難度，至於要從後頭的陣列找另外兩個對應的所有組合，如果是在無序的狀況下可能要用hashmap來找，也因為事先排序完就能同時從後頭陣列左右兩邊開始找起，當後頭陣列的最左與最右值再與前面取出的值相加大於0時，表示總合太大將右側的index向前推一點找比較小的值並重新判斷，又當總合小於0時表示太小，將左側的index向後推一點找比較大的值並再次判斷，最後如果找到剛好等於0的情況就放入結果之中，因為要找出所有可能的組合，此時就將左右兩側的index一起向內推尋找其它可能，直到左側的index比右側大才能確定已經找出所有可能。

程式碼解說:

既然知道了先排序可以減少題目不少難度，這邊一開始就用library內建來排序整個陣列，接著便開始取出陣列中的元素，正如先前所說如果下一項的元素與前一項相同不但組合可能較少還有可能完全重覆，因此就要篩出這類的情況，在確保不會有相同的情況後就可以開始找出另外兩個的所有組合(下一段)，待每個不重覆的值都找出所有組合後才回傳結果

1
2
3
4
5
6
7
8
9
10
11
12
var sum int
var front int
var rear int
var result [][]int
sort.Ints(nums)
for i, v := range nums {
	if i > 0 && v == nums[i-1] {
		continue
	}
	...
}
return result

因為是從該元素後頭的陣列找另外兩個對應的所有組合，且事先排序完就能同時從後頭陣列左右兩邊開始找起，最左邊我們就從取出值的index下一個開始，而最右邊當然就是陣列的最後一個值，一直找到當左邊的位置超過右邊才確定找完該數的所有可能，一開始當然就是先算出取出值與左右兩邊值的總合，如果總合剛好為0就將三數放入結果之中，而因為左右兩邊的值也有可能有連續相同的值，因此如果任一邊與下一項的值相同則向內推直到超出範圍或值不相等為止，最後如果總合大於0表示值太大，此時就將右邊的index向前推並再次判斷，反之如果總合小於0表示值太小則將左邊的index向後推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
front = i + 1
rear = len(nums) - 1
for front < rear {
	sum = v + nums[front] + nums[rear]
	if sum == 0 {
		result = append(result, []int{v, nums[front], nums[rear]})
		for front < rear && nums[front] == nums[front+1] {
			front++
		}
		for front < rear && nums[rear] == nums[rear-1] {
			rear--
		}
		front++
		rear--
	} else if sum > 0 {
		rear--
	} else {
		front++
	}
}

完整程式碼:

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
func threeSum(nums []int) [][]int {
	var sum int
	var front int
	var rear int
	var result [][]int
	sort.Ints(nums)
	for i, v := range nums {
		if i > 0 && v == nums[i-1] {
			continue
		}
		front = i + 1
		rear = len(nums) - 1
		for front < rear {
			sum = v + nums[front] + nums[rear]
			if sum == 0 {
				result = append(result, []int{v, nums[front], nums[rear]})
				for front < rear && nums[front] == nums[front+1] {
					front++
				}
				for front < rear && nums[rear] == nums[rear-1] {
					rear--
				}
				front++
				rear--
			} else if sum > 0 {
				rear--
			} else {
				front++
			}
		}
	}
	return result
}

總結:

要從一陣列中找出3個值總合為0的所有結果，要讓事情變的簡單就先將整個陣列做排序，接著每取一個就從該元素後頭的陣列找另外兩個對應的所有組合，好處在於事先排序能篩掉重覆的情況，如果拿的第一個元素為-1，第2~n個就會找出與-1對應的所有組合，而如果下一個元素還是-1，此時從第3~n個找出的所有組合，再與先前找的相比不但組合可能較少還有可能完全重覆，至於要從後頭的陣列找另外兩個對應的所有組合，也因為事先排序完就能同時從後頭陣列左右兩邊開始找起，當後頭陣列的最左與最右值再與前面取出的值相加大於0時，表示總合太大將右側的index向前推一點找比較小的值並重新判斷，又當總合小於0時表示太小，將左側的index向後推一點找比較大的值並再次判斷，最後如果找到剛好等於0的情況就放入結果之中，因為要找出所有可能的組合，此時就將左右兩側的index一起向內推尋找其它可能，直到左側的index比右側大才能確定已經找出所有可能。

分享到