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

L千年老妖 · · 1890 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

题目：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

}

有疑问加站长微信联系（非本文作者）