Google 面试算法真题（附程序代码+详细解析）

Google面试算法真题（附程序代码+详细解析）本次整理4道Google高频面试原题，覆盖数组、哈希、双指针、动态规划，是谷歌onsite/phonescreen核心题型。所有代码可直接运行，解析从工程角度拆解思路，贴合面试官考察重点：解题思路、边界条件、时间空间优化、代码简洁性。面试题1：两数之和（Google入门高频题）题目描述给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。默认每个输入只对应一个唯一答案，同一个数组元素不能重复使用。解题思路暴力双层循环时间复杂度太高，面试中会直接扣分。最优解法是使用哈希表，遍历数组时，记录已经遍历过的数值和下标。每遍历一个新元素，判断「目标值-当前值」是否存在于哈希表中，存在则直接返回结果，不存在则存入哈希表。全程只需要一次遍历，效率极高。完整代码（Python）python

deftwoSum(nums,target):

#建立哈希表，存储遍历过的数值:下标

hash_map={}

forindex,numinenumerate(nums):

#计算需要匹配的差值

diff=target-num

ifdiffinhash_map:

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

return[hash_map[diff],index]

#未找到则存入当前数值

hash_map[num]=index

#题目保证有解，此处仅兜底

return[]

#测试用例

if__name__=="__main__":

test_nums=[2,7,11,15]

test_target=9

print(twoSum(test_nums,test_target))

答案解析&复杂度1.执行流程：遍历第一个数2，哈希表无7，存入2:0；遍历第二个数7，差值为2，哈希表存在，返回[0,1]。2.时间复杂度：O(n)，仅一次数组遍历，哈希查询为O(1)3.空间复杂度：O(n)，最坏情况存储全部数组元素面试官考察点：能否放弃暴力解法、哈希表的使用逻辑、边界用例（负数、重复数字）面试题2：无重复字符的最长子串（Google字符串必考）题目描述给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。子串是连续的字符序列，区别于子序列。解题思路采用滑动窗口（双指针）思路，用哈希表记录字符最后出现的下标。设置左、右两个指针作为窗口边界，右指针不断右移遍历字符，若当前字符已在窗口内重复，直接更新左指针到重复字符的下一位，同时实时更新最大长度。该方法可一次遍历完成，是谷歌认可的最优解。完整代码（Python）python

deflengthOfLongestSubstring(s:str)->int:

#记录字符最后出现的索引

char_index={}

max_len=0

left=0

forright,charinenumerate(s):

#字符重复且重复位置在窗口内，移动左指针

ifcharinchar_indexandchar_index[char]>=left:

left=char_index[char]+1

#更新字符最新位置

char_index[char]=right

#更新最大长度

max_len=max(max_len,right-left+1)

returnmax_len

#测试用例

if__name__=="__main__":

print(lengthOfLongestSubstring("abcabcbb"))

print(lengthOfLongestSubstring("bbbbb"))

print(lengthOfLongestSubstring("pwwkew"))答案解析&复杂度1.核心逻辑：窗口始终保持无重复字符，遇到重复字符直接收缩左边界，避免无效遍历。2.示例：abcabcbb最长无重复子串为abc，长度3；bbbbb最长为单个字符，长度1。3.时间复杂度：O(n)，字符串仅遍历一次4.空间复杂度：O(1)，字符集固定为英文字符，存储空间常量级面试官考察点：滑动窗口思维、边界判定、窗口收缩的精准度面试题3：最大子数组和（Google动态规划经典题）题目描述给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。解题思路使用Kadane算法（谷歌面试高频动态规划思路）。核心逻辑：遍历数组时，对每个位置，判断「当前元素单独作为子数组」和「前面子数组累加当前元素」哪个值更大，保留最大值，同时全局记录最大和。无需额外dp数组，原地迭代，空间极致优化。完整代码（Python）python

defmaxSubArray(nums):

#当前子数组最大和、全局最大和

current_sum=max_sum=nums[0]

#从第二个元素开始遍历

fornuminnums[1:]:

#抉择：重新开始子数组或延续之前子数组

current_sum=max(num,current_sum+num)

#更新全局最大值

max_sum=max(max_sum,current_sum)

returnmax_sum

#测试用例

if__name__=="__main__":

test_nums=[-2,1,-3,4,-1,2,1,-5,4]

print(maxSubArray(test_nums))

答案解析&复杂度1.执行流程：示例数组最优子数组为[4,-1,2,1]，和为6。遍历中遇到负数会判断是否截断前面的子数组，避免拖累总和。2.时间复杂度：O(n)，单次遍历3.空间复杂度：O(1)，仅使用常数变量面试官考察点：动态规划思想、贪心思维、全负数边界处理面试题4：有效的括号（Google基础工程题）题目描述给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效规则：左括号必须用相同类型的右括号闭合、左括号必须以正确的顺序闭合、每个右括号都有一个对应的相同类型左括号。解题思路栈结构经典应用。建立括号映射表，遍历字符串：遇到左括号入栈，遇到右括号则弹出栈顶元素校验，不匹配直接返回false。最后栈为空则代表全部匹配成功，否则存在未闭合括号。该逻辑贴合工程栈调用逻辑，是谷歌基础编码必考题。完整代码（Python）python

defisValid(s:str)->bool:

#右括号映射左括号

bracket_map={")":"(","]":"[","}":"{"}

stack=[]

forcharins:

#右括号，需要校验

ifcharinbracket_map:

#栈为空则无匹配左括号，取栈顶

top=stack.pop()ifstackelse"#"

ifbracket_map[char]!=top:

returnFalse

else:

#左括号入栈

stack.append(char)

#栈空代表全部匹配

returnlen(stack)==0

#测试用例

if__name__=="__main__":

print(isValid("()[]{}"))

print(isValid("(]"))

print(isValid("([)]"))

答案解析&复杂度1.核心逻辑：后进先出，保证括号闭合顺序正确，解决嵌套、并列括号场景。2.边界处理：栈为空时匹配右括号，直接判定无效，规避报错。3.时