LeetCode 15 3Sum

    
        标签：
        
            LeetCode
        
            双指针
        
    发布于：2020-06-16 09:52:42
    编辑于：2021-03-17 22:48:26
    浏览量：1359

https://leetcode.com/problems/3sum/

分析

三数之和，其实说是三指针可能更合适一些。

首先肯定要对数组进行排序，不然只能暴力解了。

我们把从小到大的三个数分别记为 a，b，c。

思路大致有以下几种：

a 从前逼近，c 从后逼近，对于每一对 a 和 c，找出合适的 b。
a 从前逼近，对于每一个 a 找出合适的一对 b 和 c，其中 b 从前逼近，c 从后逼近。

当然还有其他的组合，这里不再列举。

a，c 确定找 b

class Solution {
public:
    vector<vector<int>> solutions;
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size() < 3) return solutions;
        sort(nums.begin(), nums.end());
        vector<vector<bool>> called(nums.size(), vector<bool>(nums.size(), false));
        helper(0, nums.size()-1, nums, called);
        return solutions;
    }
    
    void helper(int left, int right, vector<int>& nums, vector<vector<bool>>& called) {
        if(left>=right) return;
        if(called[left][right]) return;
        called[left][right] = true;
        
        int nextLeft = left+1;
        while(nextLeft < nums.size() && nums[nextLeft-1] == nums[nextLeft]) nextLeft++;
        int nextRight = right-1;
        while(nextRight >=0 && nums[nextRight+1] == nums[nextRight]) nextRight--;
        helper(nextLeft, right, nums, called);
        helper(left, nextRight, nums, called);
        int a = nums[left], b = nums[right];
        int target = - (a+b);
        // Binary search
        while(right-left>=2) {
            int i = left+(right-left)/2;
            if(nums[i] > target) {
                right = i;
            } else if(nums[i]==target) {
                solutions.push_back({a, b, nums[i]});
                return;
            } else {
                left = i;
            }
        }  
    }
};

这个写的很不优雅，耗时也很多，依靠一个二维布尔数组来帮助判断是否已经计算过该组合。

复杂度是 O(n^2 * log n)，因为有 O(n^2) 个 a 与 c 的组合，对于每个组合使用二分搜索找出 b，因此是 O(log n)。

a 确定，找 b 和 c

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        // We should make sure nums is not empty before call sort!
        if(nums.size() <= 2) return ans;
        sort(nums.begin(), nums.end());
        for (int a = 0; a < nums.size()-2; ++a) {
            if (a != 0 && nums[a] == nums[a-1]) continue;
            if (nums[a] > 0) break;
            int target = -nums[a];
            int b = a+1, c = nums.size()-1;
            while (b < c) {
                if (nums[b] + nums[c] == target) {
                    ans.push_back({nums[a], nums[b], nums[c]});
                    while (b < c && nums[b] == nums[b+1]) ++b;
                    while (b < c && nums[c] == nums[c-1]) --c;
                    ++b;
                    --c;
                } else if (nums[b] + nums[c] > target) {
                    --c;
                } else {
                    ++b;
                }
            }
        }
        return ans;
    }
};

这个复杂度 O(n^2)。

Links: LeetCode-15-3Sum