01 相向双指针

1 两数之和

题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

1.1 暴力做法

点击查看代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {-1, -1};
    }
};

- 时间复杂度：$$O(n^2)$$ - 空间复杂度：$$O(1)$$

1.2 优化搜索

1.2.1 改变原数组（对应提示2）

似乎可以这样。
如果说，对元素从小到大排序，然后就可以使用相向双指针加速搜索。
但是这道题要求返回元素的下标，而原地排序的话就会导致我们不知道当前遍历到的这个元素，之前的下标是谁。
因此，可以考虑将每个下标所对应的元素捆绑起来，在C++中对应的数据结构可以是pair。

点击查看代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int, int>> nums_copy; // index value
        int n = nums.size();
        for (int i = 0; i < n; ++i) { // O(n)
            nums_copy.push_back({i, nums[i]});
        }
        auto compare = [](auto& lhs, auto& rhs) -> bool {
            return lhs.second < rhs.second;
        };
        sort(nums_copy.begin(), nums_copy.end(), compare); // O(nlogn)
        int left = 0, right = n - 1;
        while (left < right) { // O(n)
            int s = nums_copy[left].second + nums_copy[right].second - target;
            if (s > 0) {
                --right;
            } else if (s < 0) {
                ++left;
            } else {
                return {nums_copy[left].first, nums_copy[right].first};
            }
        }
        return {-1, -1};
    }
};

• 时间复杂度：$$O(nlogn)$$
• 空间复杂度：$$O(n)$$

1.2.2 哈希表

点击查看代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 不改变数组，用哈希表加速搜索
        unordered_map<int, int> hash_table;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            int x = target - nums[i];
            if (hash_table.contains(x)) {
                return {i, hash_table[x]};
            } else {
                hash_table[nums[i]] = i;
            }
        }
        return {-1, -1};
    }
};

- 时间复杂度：$$O(n)$$ - 空间复杂度：$$O(n)$$

思考题

1. 如果 nums 是有序的，是否还需要哈希表？换句话说，能否做到 \(O(1)\) 额外空间？
   答：不需要。通过先对数组从小到大排序，进而采用相向双指针即可。

2. 如果要求寻找三个数，它们的和等于 target 呢？

2 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

• 根据提示1，我们意识到可以枚举x，这样问题就变成，对于固定的数x，能否找到y和z，使得两数之和等于target - x;
• 根据提示2，或许应该对数组进行排序（改变原数组）；
• 提示3，不改变原数组，利用类似哈希表的结构加速搜索？
• 注意：这道题要求对符合条件的三元组进行去重的操作。