leetcode刷题记录Array篇(1&〜Two Sum)

题目: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.

翻译:给定n个整数的数组S,S中有元素a,b,c和d,使得+ b + c + d = target? 找到数组中所有独特的四元组,给出目标的总和。
注意:解决方案集不能包含重复的四元组。

思路:思路和3sum是一样的,所以就不重复说了

直接上代码:

golang:

 package main
 import (
 "fmt"
 "sort"
 )
 func main() {
 nums := []int{-3, -2, -1, 0, 0, 1, 2, 3}
 fmt.Println(fourSum(nums, 0))
 }
 func fourSum(nums []int, target int) [][]int {
 sort.Ints(nums)
 arrLen := len(nums)
 result := make([][]int, 0, 0)
 temp := make([]int, 4, 4)
 var sum int
 for i := 0; i < arrLen-3; i++ {
 if i > 0 && nums[i] == nums[i-1] {
 continue
 }
 for j := i + 1; j < arrLen-2; j++ {
 if j>i+1&&nums[j] == nums[j-1] {
 continue
 }
 low, high := j+1, arrLen-1
 for low < high {
 sum = nums[i] + nums[j] + nums[low] + nums[high]
 if sum == target {
 temp = []int{nums[i], nums[j], nums[low], nums[high]}
 result = append(result, temp)
 for low < high && nums[low] == nums[low+1] {
 low++
 }
 for low < high && nums[high] == nums[high-1] {
 high--
 }
 low++
 high--
 } else if sum > target {
 high--
 } else {
 low++
 }
 }
 }
 }
return result

}

本文来自:简书

感谢作者:L千年老妖

查看原文:leetcode刷题记录Array篇(1&〜Two Sum)

• 编辑
• 预览