本文分享自微信公众号 - 福大大架构师每日一题（gh_bbe96e5def84）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

2021-09-10：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案

2021-09-10：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，但是数组中同一个元素在答案里不能重复出现，你可以按任意顺序返回答案。

福大大 答案2021-09-10：

使用map。
时间复杂度：O(N)。
空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
   
    nums := []int{
   1, 3, 5}
    target := 6
    ret := twoSum(nums, target)
    fmt.Println(ret)
}

func twoSum(nums []int, target int) []int {
   
    // key 某个之前的数 value 这个数出现的位置
    map0 := make(map[int]int)
    for i := 0; i < len(nums); i++ {
   
        if _, ok := map0[target-nums[i]]; ok {
   
            return []int{
   map0[target-nums[i]], i}
        }
        map0[nums[i]] = i
    }
    return []int{
   -1, -1}
}

执行结果如下：

---

左神java代码

2021-09-21：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。要

2021-09-21：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。要求：设计并实现时间复杂度为 O(log n) 的算法。

福大大 答案2021-09-21：

二分法。
时间复杂度：O(N)。
空间复杂度：O(1)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
   
    arr := []int{
   1, 2, 3, 3, 4, 6}
    target := 3
    ret := searchRange(arr, target)
    fmt.Println(ret)
    ret = searchRange2(arr, target)
    fmt.Println(ret)
}

func searchRange(nums []int, target int) []int {
   
    if len(nums) == 0 {
   
        return []int{
   -1, -1}
    }
    L := lessMostRight(nums, target) + 1
    if L == len(nums) || nums[L] != target {
   
        return []int{
   -1, -1}
    }
    return []int{
   L, lessMostRight(nums, target+1)}
}

func lessMostRight(arr []int, num int) int {
   
    L := 0
    R := len(arr) - 1
    M := 0
    ans := -1
    for L <= R {
   
        M = L + (R-L)>>1
        if arr[M] < num {
   
            ans = M
            L = M + 1
        } else {
   
            R = M - 1
        }
    }
    return ans
}

func searchRange2(nums []int, target int) []int {
   
    if len(nums) == 0 {
   
        return []int{
   -1, -1}
    }
    lv := NearestIndex(nums, target)
    rv := NearestIndex2(nums, target)
    if lv == -1 {
   
        return []int{
   -1, -1}
    }
    if rv == -1 {
   
        return []int{
   -1, -1}
    }
    if lv > rv {
   
        return []int{
   -1, -1}
    }
    return []int{
   lv, rv}
}

// 在arr上，找满足>=value的最左位置
func NearestIndex(arr []int, v int) int {
   
    L := 0
    R := len(arr) - 1
    index := -1 // 记录最左的对号
    for L <= R {
   
        mid := L + (R-L)>>1
        if arr[mid] >= v {
   
            index = mid
            R = mid - 1
        } else {
   
            L = mid + 1
        }
    }
    return index
}

// 在arr上，找满足<=value的最右位置
func NearestIndex2(arr []int, v int) int {
   
    L := 0
    R := len(arr) - 1
    index := -1 // 记录最右的对号
    for L <= R {
   
        mid := L + (R-L)>>1
        if arr[mid] <= v {
   
            index = mid
            L = mid + 1
        } else {
   
            R = mid - 1
        }
    }
    return index
}

执行结果如下：

---

左神java代码

2022-02-02：最接近的二叉搜索树值 II。 给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的 k 个值。 注意： 给定的目标值 ta

2022-02-02：最接近的二叉搜索树值 II。
给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的 k 个值。
注意：
给定的目标值 target 是一个浮点数,
你可以默认 k 值永远是有效的，即 k ≤ 总结点数,
题目保证该二叉搜索树中只会存在一种 k 个值集合最接近目标值。
拓展：
假设该二叉搜索树是平衡的，请问您是否能在小于 O(n)（n 为总结点数）的时间复杂度内解决该问题呢？
力扣272。

答案2022-02-02：

【前驱节点-目标值】和【前驱节点-目标值】，越靠近target，就取这个节点。取了前驱节点，左扩；取了后驱节点，右扩。
准备两个栈，快速支持找前驱和后继。
时间复杂度：低于O(N)。
空间复杂度：低于O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
   
    root := &TreeNode{
   val: 4}
    root.left = &TreeNode{
   val: 2}
    root.right = &TreeNode{
   val: 5}
    root.left.left = &TreeNode{
   val: 1}
    root.left.right = &TreeNode{
   val: 3}
    ret := closestKValues(root, 3.713286, 2)
    fmt.Println(ret)
}

type TreeNode struct {
   
    val   int
    left  *TreeNode
    right *TreeNode
}

func NewTreeNode(val int) *TreeNode {
   
    ans := &TreeNode{
   }
    ans.val = val
    return ans
}

// 这个解法来自讨论区的回答，最优解实现的很易懂且漂亮
func closestKValues(root *TreeNode, target float64, k int) []int {
   
    ret := make([]int, 0)
    // >=8，最近的节点，而且需要快速找后继的这么一种结构
    moreTops := make([]*TreeNode, 0)
    // <=8，最近的节点，而且需要快速找前驱的这么一种结构
    lessTops := make([]*TreeNode, 0)
    getMoreTops(root, target, &moreTops)
    getLessTops(root, target, &lessTops)
    if len(moreTops) > 0 && len(lessTops) > 0 && moreTops[len(moreTops)-1].val == lessTops[len(lessTops)-1].val {
   
        getPredecessor(&lessTops)
    }
    for k > 0 {
   
        k--
        if len(moreTops) == 0 {
   
            ret = append(ret, getPredecessor(&lessTops))
        } else if len(lessTops) == 0 {
   
            ret = append(ret, getSuccessor(&moreTops))
        } else {
   
            diffs := abs(float64(moreTops[len(moreTops)-1].val) - target)
            diffp := abs(float64(lessTops[len(lessTops)-1].val) - target)
            if diffs < diffp {
   
                ret = append(ret, getSuccessor(&moreTops))
            } else {
   
                ret = append(ret, getPredecessor(&lessTops))
            }
        }
    }
    return ret
}

func abs(d float64) float64 {
   
    if d < 0 {
   
        return -d
    } else {
   
        return d
    }

}

// 在root为头的树上
// 找到>=target，且最接近target的节点
// 并且找的过程中，只要某个节点x往左走了，就把x放入moreTops里
func getMoreTops(root *TreeNode, target float64, moreTops *[]*TreeNode) {
   
    for root != nil {
   
        if root.val == int(target) {
   
            *moreTops = append(*moreTops, root)
            break
        } else if root.val > int(target) {
   
            *moreTops = append(*moreTops, root)
            root = root.left
        } else {
   
            root = root.right
        }
    }
}

// 在root为头的树上
// 找到<=target，且最接近target的节点
// 并且找的过程中，只要某个节点x往右走了，就把x放入lessTops里
func getLessTops(root *TreeNode, target float64, lessTops *[]*TreeNode) {
   
    for root != nil {
   
        if root.val == int(target) {
   
            *lessTops = append(*lessTops, root)
            break
        } else if root.val < int(target) {
   
            *lessTops = append(*lessTops, root)
            root = root.right
        } else {
   
            root = root.left
        }
    }
}

// 返回moreTops的头部的值
// 并且调整moreTops : 为了以后能很快的找到返回节点的后继节点
func getSuccessor(moreTops *[]*TreeNode) int {
   
    cur := (*moreTops)[len(*moreTops)-1]
    *moreTops = (*moreTops)[0 : len(*moreTops)-1]
    ret := cur.val
    cur = cur.right
    for cur != nil {
   
        *moreTops = append(*moreTops, cur)
        cur = cur.left
    }
    return ret
}

// 返回lessTops的头部的值
// 并且调整lessTops : 为了以后能很快的找到返回节点的前驱节点
func getPredecessor(lessTops *[]*TreeNode) int {
   
    cur := (*lessTops)[len(*lessTops)-1]
    *lessTops = (*lessTops)[0 : len(*lessTops)-1]
    ret := cur.val
    cur = cur.left
    for cur != nil {
   
        *lessTops = append(*lessTops, cur)
        cur = cur.right
    }
    return ret
}

执行结果如下：

---

左神java代码

关于ios – 完全删除XCode Target和彻底删除xcode的介绍现已完结，谢谢您的耐心阅读，如果想了解更多关于2021-09-10：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target、2021-09-10：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案、2021-09-21：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。要、2022-02-02：最接近的二叉搜索树值 II。 给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的 k 个值。 注意： 给定的目标值 ta的相关知识，请在本站寻找。

本文标签：

• iOS
• XCode Target
• 删除
• 彻底删除xcode