iOS 高频算法面试题（含详细答案）

iOS高频算法面试题（含详细答案）前言：iOS面试算法以简单、中等难度为主，侧重基础数据结构、常规算法思维、代码简洁度，不考复杂冷门算法。以下题目为一线互联网iOS面试高频原题，答案采用Swift原生代码，适配日常开发和面试答题规范，讲解通俗接地气。一、数组基础（面试必考）1.两数之和题目描述：给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，且数组中同一个元素不能使用两遍。示例：nums=[2,7,11,15],target=9，输出：[0,1]解题思路：最优解法使用哈希表（字典），一次遍历数组，遍历过程中存储数值和对应下标。每次计算当前数值的补数（target-当前值），判断补数是否存在于字典中，存在则直接返回下标，不存在则存入当前数据。时间复杂度O(n)，空间复杂度O(n)，优于双层循环的暴力解法。swift

functwoSum(_nums:[Int],_target:Int)->[Int]{

//键：数组数值，值：对应下标

vardict=[Int:Int]()

for(index,num)innums.enumerated(){

letcomplement=target-num

ifletcomplementIndex=dict[complement]{

//找到结果，返回两个下标

return[complementIndex,index]

}

//未找到则存入字典

dict[num]=index

}

return[]

}面试加分点：主动对比暴力遍历（O(n²)）和哈希表解法的优劣，说明日常开发中优先使用哈希表优化查询效率。2.移除数组重复元素题目描述：给你一个有序数组nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。不要使用额外的数组空间，必须在原地修改输入数组。解题思路：双指针法。有序数组重复元素必然相邻，慢指针记录有效元素位置，快指针遍历数组。快慢指针元素不同时，慢指针前进并覆盖数值，最终慢指针+1即为新数组长度。swift

funcremoveDuplicates(_nums:inout[Int])->Int{

guard!nums.isEmptyelse{return0}

varslow=0

forfastin1..<nums.count{

ifnums[fast]!=nums[slow]{

slow+=1

nums[slow]=nums[fast]

}

}

returnslow+1

}二、字符串算法（iOS面试高频）1.反转字符串题目描述：编写函数，将输入的字符串反转，原地修改，不使用系统反转方法。解题思路：左右双指针，首尾交换字符，指针向中间靠拢，直到相遇。时间复杂度O(n)，空间复杂度O(1)。swift

funcreverseString(_s:inout[Character]){

varleft=0

varright=s.count-1

whileleft<right{

//交换首尾字符

(s[left],s[right])=(s[right],s[left])

left+=1

right-=1

}

}2.有效的字母异位词题目描述：给定两个字符串s和t，编写函数判断t是否是s的字母异位词。即两个字符串包含的字母完全相同，只是顺序不同。解题思路：首先判断长度，长度不同直接返回false。通过数组统计26个字母出现次数，第一个字符串字符计数+1，第二个字符串字符计数-1，最终数组全0则为异位词。swift

funcisAnagram(_s:String,_t:String)->Bool{

guards.count==t.countelse{returnfalse}

varcount=[Int](repeating:0,count:26)

letaASCII=Character("a").asciiValue!

forcharins{

letidx=Int(char.asciiValue!-aASCII)

count[idx]+=1

}

forcharint{

letidx=Int(char.asciiValue!-aASCII)

count[idx]-=1

ifcount[idx]<0{

returnfalse

}

}

returntrue

}三、链表算法（iOS中层面试必问）1.反转单链表题目描述：给你单链表的头节点head，请你反转链表，并返回反转后的链表头节点。解题思路：迭代法，定义前驱、当前、后继三个节点，逐个改变节点指向，当前节点指向前驱节点，依次遍历完成反转。该解法空间复杂度O(1)，优于递归解法。swift

//定义链表节点

classListNode{

varval:Int

varnext:ListNode?

init(){self.val=0;self.next=nil}

init(_val:Int){self.val=val;self.next=nil}

init(_val:Int,_next:ListNode?){self.val=val;self.next=next}

}

funcreverseList(_head:ListNode?)->ListNode?{

varprev:ListNode?=nil

varcurr=head

whilecurr!=nil{

//保存后继节点

letnext=curr?.next

//反转当前节点指向

curr?.next=prev

//指针后移

prev=curr

curr=next

}

returnprev

}2.链表是否有环题目描述：给你一个链表的头节点head，判断链表中是否有环。解题思路：快慢指针（龟兔赛跑），慢指针每次走1步，快指针每次走2步。如果链表有环，快慢指针一定会相遇；无环则快指针会走到末尾。swift

funchasCycle(_head:ListNode?)->Bool{

varslow=head

varfast=head

whilefast!=nil,fast?.next!=nil{

slow=slow?.next

fast=fast?.next?.next

ifslow===fast{

returntrue

}

}

returnfalse

}四、动态规划（中等难度高频题）1.爬楼梯题目描述：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶？解题思路：经典动态规划。递推公式：dp[n]=dp[n-1]+dp[n-2]。到达第n阶台阶，最后一步要么走1阶（对应n-1阶的方法数），要么走2阶（对应n-2阶的方法数）。swift

funcclimbStairs(_n:Int)->Int{

ifn<=2{returnn}

varfirst=1

varsecond=2

for_in3...n{

lettemp=first+second

first=second

second=temp

}

returnsecond

}面试点拨：优化空间复杂度，不使用数组存储dp数组，仅用两个变量迭代，适配大数场景。2.最大子数组和题目描述：给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。解题思路：贪心+动态规划，卡登算法。遍历数组，维护当前子数组和，如果当前和为负数则舍弃，重新累计，同时记录最大值。swift

funcmaxSubArray(_nums:[Int])->Int{

varcurrentSum=nums[0]

varmaxSum=nums[0]

foriin1..<nums.count{

currentSum=max(nums[i],currentSum+nums[i])

maxSum=max(maxSum,currentSum)

}

returnmaxSum

}五、常见面试手写算法（拓展必背）1.快速排序解题思路：分治思想，选取基准值，将数组分为小于、大于基准值的两部分，递归排序左右区间。iOS开发中系统sort底层即为优化后的快排，面试常考手写实现。swift

funcquickSort(_arr:[Int])->[Int]{

guardarr.count>1else{returnarr}

letpivot=arr[arr.count/2]

letleft=arr.filter{$0<pivot}

letmiddle=arr.filter{$0==pivot}

letright=arr.filter{$0>pivot}

returnquickSort(left)+middle+quickSort(right)

}2.二分查找题目描述：给定一个有序整数数组和目标值，返回目标值下标，不存在则返回-1。解题思路：有序数组专属算法，不断收缩左右区间，取中间值对比，时间复杂度O(logn)，是有序数组最优查找方式。swift

funcbinarySearch(_nums:[Int],_target:Int)->Int{

varleft=0

varright=nums.count-1

whileleft<=right{

letmid=(left+right)/2

ifnums[mid]==target{

returnmid

}elseifnums[mid]<target{