iOS常见算法1:2Sum问题(Swift语言实现)

  1. 给一个整型数组和一个目标值,判断数组中是否有两个数字之和等于目标值
    分析:
    (1)如果每次选中一个数,然后遍历整个数组,判断是否有另一个数使两者之和满足条件。这种时间复杂度为O(n^2),不是最优解。
    (2)在遍历数组的过程中,利用集合保存遍历的当前值。若集合中存在目标值减去当前值的差值,说明数组中一定有一个数与当前值之和等于目标值。这种时间复杂度为O(n),得到优化。
func twoSum(nums:[Int],_ target:Int) -> Bool {
    var set = Set<Int>()
    
    for num in nums {
        if set.contains(num) {
            return true
        }
        set.insert(num)
    }
    return false
}
  1. 给定一个整型数组中有且仅有两个数字之和等于目标值,求两个数字在数组中的序号
    分析:与问题1思路类似,这里采用字典的形式,时间复杂度为O(n)
func twoSum(nums: [Int], _ target: Int) -> [Int] {
  var dict = [Int: Int]()
        
  for (i, num) in nums.enumerated() {
    if let lastIndex = dict[target - num] {
      return [lastIndex, i]   
    } else {
      dict[num] = i
    }
  }
        
  fatalError("No valid output!")
}
  1. 虽然不是两数之和的问题,但算法思想类似的问题:字符串中的第一个唯一字符(题目来自LeetCode)
    给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
    案例: s = "leetcode",返回 0;s = "loveleetcode",返回 2.
    注意事项:您可以假定该字符串只包含小写字母。
class Solution {
    func firstUniqChar(_ s: String) -> Int {
        var dic = [Character: Bool]()
        
        for char in s {
            if let _ = dic[char] {
                dic[char] = true
            }
            else {
                dic[char] = false
            }
        }
        
        for (i,char) in Array(s).enumerated() {
            if dic[char]! == false {
                return i
            }
        }
        
        return -1
    }
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 53.计算字符 在字符串中获取字符值的数量, 可以使用字符串字符属性中的计数属性: let unusualMena...
    无沣阅读 1,141评论 0 4
  • 第2章 基本语法 2.1 概述 基本句法和变量 语句 JavaScript程序的执行单位为行(line),也就是一...
    悟名先生阅读 4,208评论 0 13
  • 笔者前言: 读完这本书,虽然很多时候忍不住质疑,但是认真体会后,我理解到这是一个几乎完全不同于我平时的运行系统,是...
    想做点输出的云宝阅读 5,625评论 0 4
  • slice(strat,end):在数组和字符串的操作方法中都存在slice方法、它类似于substring,都是...
    Jalon阅读 286评论 0 0
  • 凌晨三点的房间有些冷 一如下午三点的太阳有些热 我有些鼻塞,在朋友家没有铺垫的木头长沙发上 我从包里取出另一条长裤...
    苍狼0001阅读 847评论 0 0