三数之和、四数之和

黎 浩然/ 16 12 月, 2021/ 算法/ALGORITHMS/ 0 comments

15. 三数之和 – 力扣（LeetCode） (leetcode-cn.com)

func threeSum(nums []int) [][]int {
   sort.Ints(nums)
   result := make([][]int, 0)
   for i := 0; i < len(nums) - 2; i++ {
      if i > 0 && nums[i] == nums[i-1] {
         continue
      }
      for j, k := i + 1, len(nums) - 1; j < k;  {
         if nums[i] + nums[j] + nums[k] < 0 {
            j++
         } else if nums[i] + nums[j] + nums[k] > 0 {
            k--
         } else {
            result = append(result, []int{nums[i] ,nums[j], nums[k]})
            for ; j < k && nums[j] == nums[j+1]; j++ {
            }
            for ; j < k && nums[k] == nums[k-1]; k-- {
            }
            j++
            k--
         }
      }
   }
   return result
}

18. 四数之和 – 力扣（LeetCode） (leetcode-cn.com)

func fourSum(nums []int, target int) [][]int {
   result := make([][]int, 0)
   sort.Ints(nums)
   for i := 0; i < len(nums) - 3; i++ {
      if i > 0 && nums[i] == nums[i-1] {
         continue
      }
      for j := i + 1; j < len(nums)-2; j++ {
         if j > i+1 && nums[j] == nums[j-1] {
            continue
         }
         for k, l := j+1, len(nums)-1; k < l; {
            if nums[i]+nums[j]+nums[k]+nums[l] < target {
               k++
            } else if nums[i]+nums[j]+nums[k]+nums[l] > target {
               l--
            } else {
               result = append(result, []int{nums[i], nums[j], nums[k], nums[l]})
               for ; k < l && nums[k] == nums[k+1]; k++ {
               }
               for ; k < l && nums[l] == nums[l-1]; l-- {
               }
               k++
               l--
            }
         }
      }
   }
   return result
}