腾讯面试的一道手撕题：给一个单调递增的数组，找出所有满足a+b=

前言：

• 2020年3月28号在腾讯教育部门的一面面试中给出这样一道算法题：给一个单调递增的数组（无重复元素），找出数组中所有满足a+b=c的三个元素。
• 当时面试官说只需讲一下思路，因为第一次比较紧张，我给了一个奇葩的解法，二分+一次遍历，现在想想都觉得可笑，应该是错的，那种解法至少是，在这就不给出了，做法很low，而且情况比较复杂，容易出错😂。估计面试官放水了，很有可能因为逻辑题和其他手撕题都做出来了，姑且让我进了二面，然后二面挂了。。。好了，不多bb，直奔解法。

正文

• 这道题解法和 LeetCode 15.三数之和 类似。昨天晚上1点左右在床上睡不着，头脑非常活跃，脑袋灵光一闪，突然想到求解方法：就是逆序固定c值（下标为i），然后双指针在[0, i - 1]中移动寻找，这样的时间复杂度为：。下面给出暴力代码和优化后的代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
    public static void main(String[] args) {
        // 给一个单调递增的数组（无重复元素），找出数组中所有满足a+b=c的三个元素。
        int[] nums = new int[] { 3, 5, 8, 9, 12, 21, 27 };
//      for (int i = 0; i < 5; i++)
//          nums[i] = i;
        List<List<Integer>> list1 = new ArrayList<List<Integer>>();
        List<List<Integer>> list2 = new ArrayList<List<Integer>>();
        // 暴力
        Arrays.sort(nums);
        for (int i = 0, len = nums.length; i < len - 2; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                for (int k = j + 1; k < len; k++) {
                    if (nums[i] + nums[j] == nums[k]) {
                        list1.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        break;
                    }
                }
            }
        }
        // 逆序固定右端点i，然后双指针在[0, i - 1]移动
        for (int i = nums.length - 1, lt, rt, twoSum; i >= 2; i--) {
            lt = 0;
            rt = i - 1;
            while (lt < rt) {
                twoSum = nums[lt] + nums[rt];
                if (twoSum > nums[i])
                    rt--;
                else if (twoSum < nums[i])
                    lt++;
                else {
                    list2.add(Arrays.asList(nums[lt], nums[rt], nums[i]));
                    lt++;
                    rt--;
                }
            }
        }
        System.out.println(list1);
        System.out.println(list2);
    }
}

• 最后输出的结果都一致：

后记

• 以上就是个人思路，应该是正确的。网上好像也没什么解法。如果你觉得还有比我这解法更优秀的话或者我的做法有错误，欢迎在评论区中评论，小弟感激不尽！🤣