1035. Uncrossed Lines¶
题目信息¶
- 题号:
1035
- 难度:
Medium
- 主题:
两个数组、相等元素配对、不交叉连线
- 原题:
- 重点:
只能连接值相等的元素,每个下标最多使用一次;所选配对在两个数组中的下标顺序必须一致,避免连线相交
题目重述¶
把数组 nums1 和 nums2 分别水平排列。可以在两个数组之间画线,每条线连接一个 nums1[i] 与一个值相等的 nums2[j]。
同一个数组元素不能连接多次,并且任意两条线不能在内部相交。等价地,若选择了配对 (i1, j1) 和 (i2, j2) 且 i1 < i2,就必须满足 j1 < j2。请返回最多可以画出的线数量。
1 <= nums1.length, nums2.length <= 500,1 <= nums1[i], nums2[j] <= 2000。
自建示例¶
数值相等但顺序冲突的连接不能同时选择:
输入:nums1 = [1,3,2,4], nums2 = [3,1,4,2]
输出:2
解释:可以连接 1 与 1、2 与 2,或者连接 3 与 3、4 与 4;无法同时选择三条而保持两侧下标顺序一致。
两个数组没有共同值:
输入:nums1 = [1,2], nums2 = [3,4]
输出:0
解释:不存在值相等的元素对,因此一条线也无法画出。