深圳iava外包越来越低了，5到10年竟然最多13K或者15K了，比前几年还低

线上做接口联调的时候，我见过一个需求写成这样： “给你两个餐厅列表，找出两个人都想去，而且索引和最小的那一个。”

一眼看过去不难。真写起来，很多人会先上两层 for，暴力对撞。能过样例，但味道不对。

题目本质： 给定两个 List<String>，找公共元素，使得它在 list1 的索引 i，加上在 list2 的索引 j，i + j 最小。可能不止一个。

先别急着写代码，我一般第一反应是： 这个明显是“用空间换时间”的场景。别两层循环，先把一个列表变成可 O(1) 查询的结构。

最常见解法是： 先遍历 list1，把 value -> index 存到 Map 里。 再遍历 list2，实时计算 index 和，维护一个最小值。

直接上代码。

public List<String> findRestaurant(String[] list1, String[] list2){
    Map<String, Integer> indexMap = new HashMap<>();
for (int i = 0; i < list1.length; i++) {
        indexMap.put(list1[i], i);
    }

    List<String> result = new ArrayList<>();
int min = Integer.MAX_VALUE;

for (int j = 0; j < list2.length; j++) {
        Integer i = indexMap.get(list2[j]);
if (i != null) {
int sum = i + j;
if (sum < min) {
                result.clear();
                result.add(list2[j]);
                min = sum;
            } elseif (sum == min) {
                result.add(list2[j]);
            }
        }
    }
return result;
}

这段代码逻辑很直白，但有几个点我写的时候会特意盯一下。

第一，为什么第二轮遍历的是 list2，而不是 list1？

因为第一轮已经把 list1 放进了 Map，第二轮换个方向扫，可以避免重复判断。 其实扫谁都可以，但不要两个都扫两遍。

第二，result.clear() 这个动作很多人会忘。

当发现更小的索引和时，必须清空旧结果。否则你会把之前大的索引和结果也留着，逻辑就错了。

第三，时间复杂度。

构建 Map 是 O(n)，遍历 list2 是 O(m)，总体 O(n + m)。 暴力双循环是 O(n * m)。数据一大差距立刻拉开。

我自己刷这题时，当时还多想了一步： 能不能提前剪枝？

比如，如果当前 j 已经大于 min，那后面还用算吗？

注意一下，i 是固定的，j 在递增。 但 i 是从 map 查出来的，不一定是递增。 所以不能简单用 j > min 就 break，这种剪枝是错的。

这种题，最容易“聪明反被聪明误”的就是乱剪枝。

再说一个现场味一点的优化思路。

如果 list1 特别长，list2 很短，其实可以把短的那一份建 Map。 内存占用更小，缓存命中率更好。

稍微改一下：

public List<String> findRestaurant(String[] list1, String[] list2){
if (list1.length > list2.length) {
return findRestaurant(list2, list1);
    }

    Map<String, Integer> indexMap = new HashMap<>();
for (int i = 0; i < list1.length; i++) {
        indexMap.put(list1[i], i);
    }

    List<String> result = new ArrayList<>();
int min = Integer.MAX_VALUE;

for (int j = 0; j < list2.length; j++) {
        Integer i = indexMap.get(list2[j]);
if (i == null) continue;

int sum = i + j;
if (sum < min) {
            result.clear();
            result.add(list2[j]);
            min = sum;
        } elseif (sum == min) {
            result.add(list2[j]);
        }
    }
return result;
}

这类题没什么花活，核心就一句话：

能不能把“查找公共元素”这件事，从 O(n) 降到 O(1)。

很多所谓“数组双指针”爱好者，会想排序之后双指针走。 那就变味了——排序会破坏原始索引，题目要的是原始索引和。

刷题的时候，别机械套模板。 先看题目真正约束的是什么。

这题真正约束的是“原始索引”。

抓住这一点，解法就很自然。

写到这就够了。 这种题不靠技巧，靠的是你对时间复杂度有没有下意识的警觉。