18.4Sum.md

18. 4Sum

Hash table solution can reference 15. 3Sum, create a hash to record the number of occurrences of each number in nums. then using three for loops, and only get the first number that appears in each loop, last number using target - i - j - k to hash find. This solution time complexity is O(n³).

func fourSum(nums []int, target int) [][]int {
	var result [][]int
	sort.Ints(nums)
	set := map[int]int{}
	for _, num := range nums {
		set[num]++
	}
	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < len(nums); j++ {
			if j-1 != i && nums[j] == nums[j-1] {
				continue
			}
			for k := j + 1; k < len(nums); k++ {
				if k-1 != j && nums[k] == nums[k-1] {
					continue
				}
				t := target - nums[i] - nums[j] - nums[k]
				if t < nums[k] {
					continue
				}
				if _, ok := set[t]; !ok {
					continue
				}
				if set[t] >= 1+getOcc(nums[i], t)+getOcc(nums[j], t)+getOcc(nums[k], t) {
					result = append(result, []int{nums[i], nums[j], nums[k], t})
				}
			}
		}
	}
	return result
}

func getOcc(i, j int) int {
	if i == j {
		return 1
	}
	return 0
}