JustSong Archive Link About
Projects
Categories
Others

LeetCode 15 3Sum

Tag: LeetCode 双指针 Posted on 2020-06-16 09:52:42 Edited on 2020-06-16 10:14:56 Views: 120

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

分析

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

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

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

思路大致有以下几种:

  1. a 从前逼近,c 从后逼近,对于每一对 a 和 c,找出合适的 b。
  2. 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)。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/