18. 4Sum

題目連結

思路

本題為 3Sum 的延伸，不過除了從三個數字拓展到四個數字之外，同時也不再是只要求總和為 0，而是根據輸入的 target 做為目標的總和值。本題的解題思路和 3Sum 類似，一樣是會運用到雙指標來進行總和的搜尋比對，不過和 3Sum 最大的差異有以下兩點：

1. 由於總和的目標是 target 而非固定為 0，因此無法藉由 nums[i] > 0 來斷定是否已經沒有組合的可能

2. 加總的數字從 3 個變成 4 個，扣除掉雙指標的兩個數字，需要在之前先用兩個迴圈來進行去除重複的操作

其餘的概念基本上都可以直接延續使用，外層會有雙迴圈來處理前兩個數字的重複性，內層引入雙指標來進行組合的搜尋，並在找到之後對雙指標進行重複數字的排除，另外外層雙迴圈遍歷的終點也是會需要注意小心維護的地方。

Full Code

Golang

func fourSum(nums []int, target int) [][]int {
    if len(nums) < 4 {
		return nil
	}
    
	sort.Ints(nums)
	var results [][]int

	for i := 0; i < len(nums)-3; i++ {
		n1 := nums[i]
      
		if i > 0 && n1 == nums[i-1] {
			continue
		}

		for j := i + 1; j < len(nums)-2; j++ {
			n2 := nums[j]
          
			if j > i+1 && n2 == nums[j-1] {
				continue
			}

			left := j + 1
			right := len(nums) - 1
          
			for left < right {
				n3 := nums[left]
				n4 := nums[right]
				sum := n1 + n2 + n3 + n4
              
				if sum == target {
					results = append(results, []int{n1, n2, n3, n4})
                  
					for left < right && n3 == nums[left+1] {
						left++
					}
					for left < right && n4 == nums[right-1] {
						right--
					}
                  
					left++
					right--
				} else if sum < target {
					left++
				} else {
					right--
				}
			}
		}
	}
  
	return results
}