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

L千年老妖 · · 1180 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

入群交流(和以上内容无关):Go中文网 QQ 交流群:798786647 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

1180 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传