1. twoSum 问题

我先来编一道 twoSum 题目：

如果假设输入一个数组 nums 和一个目标和 target，请你返回 nums 中能够凑出 target 的两个元素的值，比如输入 nums = [1,3,5,6], target = 9，那么算法返回两个元素 [3,6]。可以假设只有且仅有一对儿元素可以凑出 target。

我们可以先对 nums 排序，然后利用写过的左右双指针技巧，从两端相向而行就行了：

// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。
 
// 参数 nums 是长度为 n 的数组，target 是目标值
// 返回长度为 2 的数组，表示 nums 中恰好有两个元素的和为 target
public int[] twoSum(int[] nums, int target) {
    // 先对数组排序
    Arrays.sort(nums);
    // 左右指针
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // 根据 sum 和 target 的比较，移动左右指针
        if (sum < target) {
            lo++;
        } else if (sum > target) {
            hi--;
        } else if (sum == target) {
            return new int[]{nums[lo], nums[hi]};
        }
    }
    return new int[]{};
}
 

这样就可以解决这个问题，力扣第 1 题「 两数之和 」和力扣第 167 题「 两数之和 II - 输入有序数组 」稍加修改就可以用类似的思路解决，我这里就不写了。