未分類

4Sum

Array, Go, HashTable, LeetCode, TwoPointers

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

For example:

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

Default:

1
2
3
func fourSum(nums []int, target int) [][]int {
}

解答思路:

建議可以先參考先前3Sum的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼稍做增加而已，如果可以找出三個總合為0的所有組合，當然要再找4Sum或更多就不會差太多。

要從一陣列中找出4個值總合與目標值相同總合的所有組合，一樣先將整個陣列做排序，不過這次是取兩個值才從該元素後頭的陣列找另外兩個對應的所有組合，因為對後面兩個值來說只是藉由排序好的數列以左右兩邊找匹配的剩餘總合，所以只要前面總合沒有重覆的情況，最後兩個自然會找出對應且不重覆的所有組合，至於前面取兩個值的方式，其實和只有一個的取值方式相同，就是取值的同時判斷是否與先前取的值相同，只是這次變成了巢狀迴圈罷了，或者可以用hashmap來儲存前面兩個的總合來看是否出現重覆的情況，畢竟對後面兩個做匹配的來說只要不重覆即可，不過都已經排序了還用hashtable來處理會有點奇怪。

程式碼解說:

對照先前3Sum的程式碼，主要只有修改取值的同時判斷是否與先前取的值相同的部分，這次只是外頭再多了一層迴圈做一樣的事，唯一要注意的是因為是取兩個值，所以裡面那層迴圈j初始值為上一層迴圈i值+1，當然j也要比i+1大才能判斷是否與先前取的值相同，最後才是從後頭的陣列找另外兩個對應的所有組合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var result [][]int
sort.Ints(nums)
for i, v := range nums {
	if i > 0 && v == nums[i-1] {
		continue
	}
	for j := i + 1; j < len(nums); j++ {
		if j > i+1 && nums[j] == nums[j-1] {
			continue
		}
		...
	}
}
return result

完整程式碼:

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
func fourSum(nums []int, target 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
		}
		for j := i + 1; j < len(nums); j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			front = j + 1
			rear = len(nums) - 1
			for front < rear {
				sum = v + nums[j] + nums[front] + nums[rear]
				if sum == target {
					result = append(result, []int{v, nums[j], 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 > target {
					rear--
				} else {
					front++
				}
			}
		}
	}
	return result
}

總結:

建議可以先參考先前3Sum的解法，解說較為詳細，基本上概念完全一樣。

要從一陣列中找出4個值總合與目標值相同總合的所有組合，一樣先將整個陣列做排序，不過這次是取兩個值才從該元素後頭的陣列找另外兩個對應的所有組合，因為對後面兩個值來說只是藉由排序好的數列以左右兩邊找匹配的剩餘總合，所以只要前面總合沒有重覆的情況，最後兩個自然會找出對應且不重覆的所有組合，至於前面取兩個值的方式，其實和只有一個的取值方式相同，就是取值的同時判斷是否與先前取的值相同，只是這次變成了巢狀迴圈罷了，或者可以用hashmap來儲存前面兩個的總合來看是否出現重覆的情況，畢竟對後面兩個做匹配的來說只要不重覆即可，不過都已經排序了還用hashtable來處理會有點奇怪。

分享到