Golang每日一练(leetDay0078) 存在重复元素 II\III ContainsDuplicate

2023-05-29 113

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Golang每日一练(leetDay0078) 存在重复元素 II\III ContainsDuplicate

219. 存在重复元素 II Contains Duplicate ii

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3

输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1

输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2

输出：false

提示：

1 <= nums.length <= 10^5

-10^9 <= nums[i] <= 10^9

0 <= k <= 10^5

代码：

package main
import (
  "fmt"
)
func containsNearbyDuplicate(nums []int, k int) bool {
  n := len(nums)
  for i := 0; i < n; i++ {
    for j := i + 1; j < n; j++ {
      if nums[i] == nums[j] && abs(i-j) <= k {
        return true
      }
    }
  }
  return false
}
func containsNearbyDuplicate2(nums []int, k int) bool {
  n := len(nums)
  m := make(map[int]int)
  for i := 0; i < n; i++ {
    if j, ok := m[nums[i]]; ok && abs(i-j) <= k {
      return true
    }
    m[nums[i]] = i
  }
  return false
}
func containsNearbyDuplicate3(nums []int, k int) bool {
  n := len(nums)
  m := make(map[int]int)
  for i := 0; i < n; i++ {
    if i > k {
      delete(m, nums[i-k-1])
    }
    if j, ok := m[nums[i]]; ok && abs(i-j) <= k {
      return true
    }
    m[nums[i]] = i
  }
  return false
}
func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}
func main() {
  nums := []int{1, 2, 3, 1}
  fmt.Println(containsNearbyDuplicate(nums, 3))
  nums = []int{1, 0, 1, 1}
  fmt.Println(containsNearbyDuplicate(nums, 1))
  nums = []int{1, 2, 3, 1, 2, 3}
  fmt.Println(containsNearbyDuplicate(nums, 2))
  nums = []int{1, 2, 3, 1}
  fmt.Println(containsNearbyDuplicate2(nums, 3))
  nums = []int{1, 0, 1, 1}
  fmt.Println(containsNearbyDuplicate2(nums, 1))
  nums = []int{1, 2, 3, 1, 2, 3}
  fmt.Println(containsNearbyDuplicate2(nums, 2))
  nums = []int{1, 2, 3, 1}
  fmt.Println(containsNearbyDuplicate3(nums, 3))
  nums = []int{1, 0, 1, 1}
  fmt.Println(containsNearbyDuplicate3(nums, 1))
  nums = []int{1, 2, 3, 1, 2, 3}
  fmt.Println(containsNearbyDuplicate3(nums, 2))
}

输出：

true

false

true

false

true

false

220. 存在重复元素 III Contains Duplicate iii

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0

输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2

输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3

输出：false

提示：

0 <= nums.length <= 2 * 10^4

-2^31 <= nums[i] <= 2^31 - 1

0 <= k <= 10^4

0 <= t <= 2^31 - 1

代码：

package main
import (
  "fmt"
)
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
  n := len(nums)
  if n < 2 || k < 1 || t < 0 {
    return false
  }
  buckets := make(map[int]int)
  w := t + 1
  for i := 0; i < n; i++ {
    if i > k {
      delete(buckets, getBucketId(nums[i-k-1], w))
    }
    bucketId := getBucketId(nums[i], w)
    if _, ok := buckets[bucketId]; ok {
      return true
    }
    if v, ok := buckets[bucketId-1]; ok && abs(nums[i]-v) <= t {
      return true
    }
    if v, ok := buckets[bucketId+1]; ok && abs(nums[i]-v) <= t {
      return true
    }
    buckets[bucketId] = nums[i]
  }
  return false
}
func getBucketId(x, w int) int {
  if x >= 0 {
    return x / w
  }
  return (x+1)/w - 1
}
func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}
func main() {
  nums := []int{1, 2, 3, 1}
  fmt.Println(containsNearbyAlmostDuplicate(nums, 3, 0))
  nums = []int{1, 0, 1, 1}
  fmt.Println(containsNearbyAlmostDuplicate(nums, 1, 2))
  nums = []int{1, 5, 9, 1, 5, 9}
  fmt.Println(containsNearbyAlmostDuplicate(nums, 2, 3))
}