Question 1:
You are given two arrays with positive integers arr1 and arr2.
A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, 123 is a prefix of the integer 12345, while 234 is not.
A common prefix of two integers a and b is an integer c, such that c is a prefix of both a and b. For example, 5655359 and 56554 have a common prefix 565, while 1223 and 43456 do not have a common prefix.
You need to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.
Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0.
Example 1:
Input: arr1 = [1,10,100], arr2 = [1000]
Output: 3
Explanation: There are 3 pairs (arr1[i], arr2[j]):
- The longest common prefix of
(1, 1000)is1. - The longest common prefix of
(10, 1000)is10. - The longest common prefix of
(100, 1000)is100.
The longest common prefix is 100 with a length of 3.
Question 2:
You are given a 0-indexed array nums and an integer target. A 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself.
Return the length of the shortest subarray of infinite_nums with a sum equal to target. If there is no such subarray, return -1.
Example 1:
Input: nums = [1,2,3], target = 5
Output: 2
Explanation: In this example infinite_nums = [1,2,3,1,2,3,1,2,...]. The subarray in the range [1,2] has the sum equal to target = 5 and length = 2. It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.
Example 2:
Input: nums = [1,1,1,2,3], target = 4
Output: 2
Explanation: In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...]. The subarray in the range [4,5] has the sum equal to target = 4 and length = 2. It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.
Example 3:
Input: nums = [2,4,6,8], target = 3
Output: -1
Explanation: In this example infinite_nums = [2,4,6,8,2,4,6,8,...]. It can be proven that there is no subarray with sum equal to target = 3.
这组题目都很适合面试中的数组与前缀思想训练。第 1 题本质上是把每个整数转成字符串后比较前缀，常见做法是用 Trie 按数字位建立前缀树，或者把数字前缀逐层哈希 / 排序后求最大公共前缀长度；关键是高效找到两个数组中任意一对数字的最长共同起始数字串。第 2 题则是无限循环数组上的最短子数组和问题，通常要结合前缀和与滑动窗口 / 双指针来处理跨越数组边界的情况，先判断是否能通过若干整段数组贡献接近 target，再在有限展开范围内寻找最短长度。
